(navigation image)
Home American Libraries | Canadian Libraries | Universal Library | Community Texts | Project Gutenberg | Children's Library | Biodiversity Heritage Library | Additional Collections
Search: Advanced Search
Anonymous User (login or join us)
Upload
See other formats

Full text of "An introduction to local area networks"

274 Spring Joint Computer Conference, 1972 
Figure 3--The lsyer of protocol 
tions are often'provided (e.g., saving a transcript of a 
session in a local file, sending a file in place of user- 
typed input, reporting whether various HOSTs are or 
have been up). 
In the serving HOST it is desirable that a process 
controlled over the ARPANET behave as it would if 
controlled locally. The cleanest way to achieve this 
goal is to generalize the terminal c6trol portion (TCP) 
of the operating system to accept ARPANET terminal 
interaction. It is unpleasant to modify any portion of 
a working computer system and modification could bc 
avoided if it were possible to use a non-supervisor 
process (e.g., "Server-TELNET" or "LOGGER") to 
perform the job creation, login, terminal input-output, 
interrupt, and logout functions in exactly the same way 
USING HOST 
ii! Terminal Control 
Figure 4--Dat flow for remote interactive 
------------------------------<page break>-----------------------------
Function-Oriented Protocols for ARPA Computer Network 275 
Figure b--Data flow scheme for server 
as a direct console user. Prior to the development of the 
ARP.ANET, no operating system provided these func- 
tions to non-supervisor processes in anywhere near the 
requid completeness. Some systems have since been 
modified to support this generalized job control scheme. 
See Figures 5 and 6. 
Efforts to standardize communications in the TEL- 
NET protocol focused on four issues: character set, 
echoing, establishing connections, and attention 
handling. 
The chosen character set is 7-bit ASCII in 8-bit 
fields with the high-order bit off. Codes with the high- 
order bit on are reserved for TELNET control func- 
tions. Two such TELNET cp.trol function codes are 
the "long-space" which stands for the 200 millisecond 
space generated by the teletype BREAK button, and 
the synchronization character (SYNCH) discussed be- 
low in conjunction with the purpose of the TELNET 
interrupt signal. 
Much controversy existed regarding echoing. The 
basic problem is that some systems expect to echo, 
while some terminals always echo locally. A set of con- 
ventions and signals was developed to control which 
side of a TELNET connection should echo. In practice, 
those systems which echo have been modified to include 
provision for locally echoing terminals. This is a non- 
trivial change affecting many parts of a serving HOST. 
For example, normally echoing server HOSTs do not 
echo passwords so as to help maintain their security. 
Terminals which echo locally defeat this strategy, how- 
M 
LOGGER must be a background service program capable of initiating jobs 
gure 6--Alternate data flow scheme for a aerver 
------------------------------<page break>-----------------------------
276 Spring Joint Computer Conference, 1972 
N( 
 Figure 7--Data flow and processing of the character 
input stream 
ever, and some other protection scheme is necessary. 
Covering the password with noise characters is the 
usual solution. 
The HOST-HOST protocol provides a large number 
of sockets for each HOST, but carefully refrains from 
specifying which ones arc to be used for what. To estab- 
lish communication between a user-TELNET and a 
servcr-TELNET some convention is required. The 
Initial Connection Protocol (iCP)  is used: 
1. Connection is initiated from a uscr-TELNET's 
receive socket to a scr4ng HOST's socket 1 
(a send socket). 
2. When the initia} connection is established, the 
serving HOST sends a generated socket number 
and closes the connection. This socket number 
identifies an adjacent socket pair at the serving 
HOST through which the uscr-TELNET can 
communicate with a scrvcr-TELNET. 
3. TELNET connections are then initiated be- 
tween the now specified pairs of sockets. Two 
connections arc used to provide hi-directional 
communication. 
Note that sockct 1 at the serving HOST is in use only 
long enough to send another socket number with whic} 
to make the actual service connections. 
One of the functions performed by a terminal control 
program within an operating system is the scanning of 
an input stream for attention elmracters intended to 
stop an errant process and to return control to the 
executive. Terminal control programs whic} . buffer in- 
put sometimes run out of space. When this imppens to 
a local trminal's input stream, a "bell" or a question 
mark is echtx.d and the overflow charteter discarded, 
after chcckf1 It, .see f it i.s t&' attc,tit, character. See 
Figure 7. This strategy works well in peaelite, bul it 
depends rather strongly on the inlelligenec of the human 
user, the invariant time de}ay in the input transmission 
system, and a }ack of buffering between type-in and at- 
tention checking. None of these c0hflitions exists for 
interactive traffic over the net: The serving ttOST can- 
not control the speed (except to slow it down) or tim 
buffering within the using HOST, nor can it even know 
whet}tee a human user is supplying the input. It is thus 
necessary that the terminal control program or server- 
TELNET not, in general, discard characters from a net- 
work input stream; instead it must suspend its am'cpt- 
ance of characters via the HOST-HOST flow control 
mechanism. Since a HOST may only send messages 
when there is rm at the destination, the responsibility 
for dealing with too much input is thus transferred back 
to the using HOST. This scheme asres that no charac- 
ters accepted by the using HOST are inadvertently lost. 
However, if the process in the serving HOST stops 
eepting input, the pipeline of buffera between the user- 
TELNET and remote process will fill up so that. atten- 
tion charactcm cannot get through to the serving 
executive. In the TELNET protocol, the solution to 
this problem ca}ls for the user-TELNET to send, on 
request, a HOST-HOST interrupt signal forcing the 
server-TELNET to switch input modes to process net- 
work input for attention charcetera. The server- 
TELNET is required to scan for attention characters 
in its network input, even if some input must be dis- 
carded while doing so. The effect of the interrupt signal 
to a server-TELNET from its user is to cause the bur- 
fern between them to be emptied for the priority pro- 
ceding of attention charcetera. 
To flip an attention scanning server-TELNET back 
into its normal mode, a special TELNET synchroniza- 
tion character (SYNCH) is defined. When the server- 
TELNET encountem this character, it returns to the 
strategy of accepting terminal input only ms buffer 
space permits. There is a possible race condition if the 
SYNCH character arrives before the ttOST-HOST 
interrupt signal, but the race is handled by keeping 
a count of SYNCHs without matching signa}s. Note 
that attention characters are IIOST specific and may 
b(' any of 129 c}mractcrs--128 ASCII plus "long 
space"--while SYNCH is a TELNET control character 
recognized by all server-TELNETs. It would not do 
to use the ttOST-HOST signal alone in place of the 
signal-SYNCH combination in attention processing, 
because the position of the SYNCII c}mractcr in the. 
TELNET input tretm is required to determine w}mrv 
attentmn processing (rods and where norma'. mode input 
proceding begimp. 
------------------------------<page break>-----------------------------
Function-Oriented Protocols for ARPA Computer Network 277 
FILE TRANSFER 
When viewing the ARPANET msa disributed 
computer operating system, one initial question is that 
of how to construct a distributed file system. Although 
it is constructive to entertain speculation on how the 
ultimate, automated distributed file system might look, 
one important first step is to provide for the simplest 
kinds of explicit file transfer to support early sub- 
stantive use. 
During and immediately after the construction of the 
ARPANET user-level process in[efface, several ad hoc 
file transfer mechanisms developed to provide support 
for initial use. These mechanisms took two forms: (1) 
use of the TELNET data paths for text file transfer and 
(2) use of raw byte-stream communication between 
compatible systems. 
By adding two simple features to the user-TELNET, 
text file transfer became an immediate reality. By 
adding a "SCRIPT" feature to user-TELNETS 
whereby all text typed on the user's console can be 
directed to a file on the user's local file system, a user 
need only request of a remote HOST that a partidular 
text file be typed on his console to get that file trans- 
ferred to his local file system. By adding a "SEND- 
FILE" feature to a user-TELNET whereby the con- 
tents of a text file can be substituted for console type-in, 
a user need only start a remote system's editor as if to 
enter new text and then send his local file as type-in 
to get it transferred to the remote file system. Though 
etude, both of these mechanisms have been used with 
much success in getting real work done. 
Between two identical systems it has been a simple 
matter to produce programs at two ends of a connection 
to copy raw bib from one file system to another. This 
mechanism has also served well in the absence of a more 
general and powerful file transfer system. 
Brays in which these early ad hoc file transfer mech- 
anisms are deficient are that (1) they require explicit 
and often elaborate user intervention and (2) they de- 
pend a great deal on the compatibility of the file sys- 
tems involved. There is an on-going effort to construct 
a File Transfer Protocol (FTP) .' worthy of wide 
implementation which will make it possible to exchange 
structured sequential files among widely differing file 
systems with a minimum (if any) explicit user inter- 
vention. In short, the file transfer protocol being 
velopcd provides for the connection of a file transfer 
user process ("user-FTP") and file transfer server 
process ("server-FTP") according to the Initial Con- 
neetion Protocol discussed above. See Figure S. A user 
will be able to request that specific file manipulation 
operations be performed on his behalf. The 1.'lie Trans- 
for Protocol will support file operations including (1) 
Figure 8--Data flow for file transfer 
list remote directory, (2) send local file, (3) retrieve re- 
mote file, (4) rename remote file, and (5) delete remote 
file. 
It is the intention of the protocol designers to regu- 
larize the protocol so that file transfer commands can 
be exchanged by consoles file transfer jobs engaged in 
such exotic activities as automatic back-up and dy- 
namic file migration. The transfers enwisioned will be 
accompanied with a Data Transfer Protocol (DTP) i 
rich enough to preserve sequential file structure and in 
a general enough way to permit data to flow between 
different file systems. 
USING THE ARPANET FOR REMOTE 
JOB ENTRY 
A very important use of the ARPANET is to give a 
wide community of users access to specialized facilities. 
One type of facility of interest is that of a very powerful 
number-cruncher. Users in the distributed ARPANET 
community need to have access to powerful machines 
for compute-intensive applications and the mode of 
operation most suited to these uses has been batch 
Remote Job Entry (RAE). Typically, a user will generate 
a "deck" for submission to a batch system. See Figure 9. 
He expects to wait for a period on the order of tens of 
minutes or hours for that "deck"  be processed, and 
then t.o receive the usually voluminous output thereby 
generated. See Figure 10. 
As in the case of file transfer, there are a few useful 
ad 2, oc ARPANET RJE protocols. A standard RJE 
protocol is being developed to provide for job sub- 
ntission to a number of facilities in the ARPANET. 
This protocol is being constructed using the TELNET 
and File Transfer protocols. A scenario which sketches 
how the protocol provides the RJE in the simplest, 
most explicit way is as follows: 
Via an Al{PANET tkJE process, a user connects his 
------------------------------<page break>-----------------------------
278 Spring Joint Computer Gorffercnce, 1972 
System Control 
Prelm red "deck" 
Queue of 
$uhmi t ted Jobs 
Figure 9---Submiion of RJE input 
terminal to an RJE server process at the HOST to 
which he intends to submit his job "deck." Through 
a short dialogue, he establishes the source of his input 
and initiates its transfer using the File Transfer Proto- 
col. At some later time, the user rcconnects to the 
propriate R$E server and makes an inquiry on the 
NEP i'.. Server 
File Svs tern 
Figure 10--Ftetricval of Pale output 
------------------------------<page break>-----------------------------
Function-Oriented Protocols for ARPA Computer Network 279 
status of his job. When notified that his input has becn 
proccsscd, Lic tt,cn issues commands to the serving 
HOST to transfer his output. back. 
We can of course imagine more automatic ways of 
achieving these same functions. A user might need only 
type a job submission command to his local system. 
Automatically and invisibly, then, the local system 
would connect and convcrsc with the specified RJE 
server causing the dcsircd output to later appear in the 
users file area or perhaps on a local line printer. The 
intention is to design the RJE protocol so that the ex- 
plicit use can start immediately and the more automatic 
tE systems can be built as desired. 
OTHER PROTOCOLS AND CONCLUSIONS 
One of the more difficult problems in utilizing a net- 
work of diverse computers and operating systems is that 
of dealing with incompatible data streams. Computers 
and 'heir language processors have many ways of 
representing data. To make use of different computers 
it is necessary to (1) produce a mediation scheme for 
each incompatibility or (2) produce a standard repre- 
sentation. There are many strong arguments for a 
standard representation, but it has been hypothesized 
that if there were a simple way of expressing a limited 
set of transformations on data streams, that a large 
number of incompatibilities could be resolved and a 
great deal of computer-computer cooperation expedited. 
The bulk of protocol work is being done with the 
invention of standard representations. The TELNET 
protocol, as discussed, is founded on the notion of a 
standard terminal called the Network Virtual Terminal 
(NVT). The File Transfer Protocol is working toward 
a standard sequential file (a Network Virtual File?). 
So it is also with less advanced protocol work in graphics 
and data management. 
There k one experiment which is taking the trans- 
formational approach to dealing with incompatibilities. 
The Data thzconfiguration Scrvicc (DIS) is to be 
generally available for mediating between incompatible 
stream configurations as directed by user-suppLied 
transformations.  
ACKNOWLEDGMENTS 
Function-oriented protocols havc been the principal 
concern of the ARPANET Network Working Group 
(NWG). A list of people who havc contributed to the 
development of the protocols discussed would include, 
Robert Bradcn, Howard Brodic, Abhay Bhushan, 
Steve Cart, Vint Ccrf, Will Crowther, Eric Harslcm, 
Peggy Karp, Charles Kline, Douglas McKay, Alex 
McKenzie, John Melvin, Ed Meyer, Jim Michcncr, 
Tom O'Sullivan, Mike Padlipsky, Aric Shoshani, Bob 
Sundberg, A1 Vczza, Dave Walden, Jim White, and 
Stcvc Wolfe. We would like to acknowledge the contri- 
bution of these researchers and vthcrs in the ARPA 
Network Working Group, without assigning any re- 
sponsibiLity for the content of this paper. 
REFERENCES 
ROBERTS 
B D WESSLER 
Computer network development to achieoe retylzrc. e shrig 
AFIPS Conference Proceedings May 1970 
2 F E HEART et al 
The interface message processor for the A RPA 
computer network 
AFIPS Conference Proceeding May 1970 
3 L KLEINROCK 
Arlytic and sa'mulation methods in cornpurr 
network design 
AFIPS Conference Proceeding May 1970 
4 H FRANK I T FRISCH W CHOU 
Topoloical consideratiors in the design of the A RPA 
Computer network 
AFIPS Conference Proceeding May 1970 
5 SpecificaJfirs for the iaterconnectlon of a Host and an IMP 
Bolt Ber&nck and Newman Inc tport No 1822 
February 1971 
6 C S CARR S D CROCKER V G CERF 
HOST-HOST communication protocol in the 
A RPA Network 
AFIPS Conference Procecding May 1970 
7 HOST/HOST protocol for the ARPA Network 
ARPA Network Information Center If7147 
8 T O'SULLIVAN et 
TELNET protocol 
ARPA Network WorFAng Group Request For 
Comments (RFC) 158 ARPA Network Information 
Center (NIC) 6768 Ms). 1971 
9 S M ORNSTEIN et &l 
The Terminal IMP for the A RPA Computer Network 
AFIPS Conference Proceedings May 1972 
10 J B POSTEL 
Offcia! initial connection protocol 
ARPA Network Working Group Document 2 NIC 
#7101 June 1971 
11 A K BHUSHAN et 
The data trarfcr protocol 
RFC 264 NIC 7812 November 1971 
12 A K BHUSIIAN ct 
The jle tranzfcr protocol 
RFC 265 NIC 7813 November 1971 
13 R ANDEILSON ct al 
The dta reconyifruratWn service--An expcr'ment 
in adaptable procezs /proccss cora.unicaton 
The ACM/IEEE Second Symposium On Problems 
The Op.imization Of Data Commuxications Systems 
October 1971 
------------------------------<page break>-----------------------------
TIP USER 
DIALOGUE 
E 
HELLO 
 HOST 
23 
C  LOGIN 
TR OPEN 
LOG ON  
I 
I 
I 
I 
I 
LOG OFF * 
- CLOSE 
TR 
CLOSED 
------------------------------<page break>-----------------------------
McROSSA multi-computer programming system* 
by ROBERT H. THOMAS and D. AUSTIN HENDERSON 
Bolt, Beranek and Newman, Inc. 
C.mbridge, Maachtmetts 
INTRODUCTION 
This paper describes an experimental "distributed" 
programming system which makes it, possible to create 
multi-computer programs and to run them on com- 
puters connected by the ARPA computer network 
(ARPANET)2 The programming system, which is 
called McROSS (for Multi-Computer Route Oriented 
Simulation System), is an extension of a single- 
computer simulation system for modelling air traffic 
situations: developed by Bolt, Beranek and Newman, 
Inc. (BBN) as a tool for air traffic control research. 
The Mc.ZOSS system provides two basic capabilities. 
One is the ability to program air traffic simulations 
composed cf a number of "parts" which run in geo- 
graphically separated computers, the distributed parts 
forming the nodes of a "simulator network." The 
second is the ability of such a simulator network to 
permit programs running at arbitrary sites in the 
ARPANET to "attach" to particular nodes in it for the 
purpose of remotely monitoring or controlling the 
node's operation. 
The McROSS distributed programming system is 
unique in several ways: 
(a) Use of McROSS generates inter-computer traffc 
in which a group of programs are engaged in 
substantive conversation. There is relatively 
little previous experience with such inter- 
computer, program-to-program conversations. 
(b) The component nodes of a simulator network 
are not bound to particular ARPANET sites 
until simulation "run time." Thus on different 
runs the same distributed program can be dis- 
tributed in different ways over the ARPANET. 
For example, in one run all the nodes of a simu- 
 This work waa supported by the Advanced Projects Research 
Agency of the Department of Defense under Contract No. 
DAH C-71-C-0088. 
(c) 
later network might be run at BBN and on the 
next some might be run at BBN, others at 
RAND and still others at the University of 
Utah. This mode of using the ARPANET is 
significantly different from the normttl one in 
which programs are bound to particular net- 
work sites at program composition time. (The 
only constraint on the binding of nodes to 
ARPANET sites is the requirement that each 
node run on a PDP-10 under the TENEX 
operating sysl em2) 
The responsibilities of a node in a simulator net- 
work can be conveniently partitioned into sub- 
tasks which can be performed more or less 
independently of one another. The MeROSS 
implementation mirrors this partitioning. Func- 
tions performed at the nodes are realized by 
groups of loosely connected, concurrently evolv- 
ing processes. 
The distributed simulation system represents an 
initial step in an on-going research program which is 
investigating techniques to make it easy to ereate, run 
and debug computations involving the coordinated be- 
havior of many computers. The MeR. OSS system is 
intended to serve both as an experimental vehicle for 
studying problems related to distributed computation 
and a.$ a tool for air traffic control research. Its two 
goals are well matched. A satisfactory solution to the 
nation's air traffic problems is likely to include a net- 
work of airborne and ground based computers working 
together on a single distributed computation: the 
scheduling and control of aircraft maneuvers. Thus, the 
air traffic control problem is a rich source of interesting 
problems in partitioned computation which can be used 
to measure the usefulness of the distributed computa- 
tional techniques developed. 
This paper is a report on ore' phae of a continuing 
research program. The intent is to describe interesting 
aspects of an experimental distributed programming 
281 
------------------------------<page break>-----------------------------
282 Spring Joint Computer Conference, 1972 
system and to share our experience with others con- 
sidering the construction of such systems. The paper 
does no more than hint at how the IX{cROSS system 
can be used in air traffic controt research. 
The next, section provides background useful for 
subsequent discussion of the distributed programming 
syslem. After than, Ire McROSS system is described, 
first in terms of the facilities it provides for creating 
distributed simulations, and then in terms of interesting 
aspects of its implementation. The paper closes with a 
discussion of some of tile issues brought into focus by 
the experience of implementing and using a distributed 
programming system. 
COMPONENTS OF THE MeROSS SYSTEM 
The main components of the distributed program- 
ming system are: 
1. The AI(PA computer network; 
2. Tbe TENEX operating system for the PDP-10; 
3. A simulation programming system knom as 
ROSS (for Route Oriented Simulation System) 
These components became operational within 5-10 
months of one another, at which time it became feasible 
to implement the distributed programming system 
being described. 
The ARPANET 
The ARPA computer network .a. is a set of auton- 
omous computer systems (hosts) which are intercon- 
nected to permit resource sharing betwccn any pair of 
them. The goal of the ARPANETqs for each host to 
make its resources accessible from other hosts in the net 
thereby permitting persons or programs residing at one 
network site to use data and programs that rcsidc and 
run at any other. Each host interfaces with the network 
through an Interface Message Processor (IMP)/ a 
small dedicated general-purpose computer. The IMPs, 
which reside at the various ARPANET sites, arc con- 
neeted by 50 kilobit common carrier lines and arc 
programmed to implement a store and forward com- 
munication network. In pssing from host A to host B 
a message pscs from host A to IMP A, through the 
IMP communication network from IMP A to IMP B 
(in general passing through a number of intermediate 
IMPS) and finally from IMP B to host B. 
At each host there is a Network Control Program 
(NCP) whose function is to provide an interface be- 
tween the network and processe, wif. hin the host. The 
NCPs use the IMP store and forward network to pro- 
vide processes with a connection switching network. 
Thus, they enable processes in different hosts to estab- 
lish connections with one another and to exchange 
information without directly concerfing themselves 
with details of network implementation such ms the 
way in which hosts are connected to and communicate 
with IMPs. 
Information can flow in only one direction on an 
ARPANET connection. Thus, before two processes are 
able to engage in a dialogue they must establish two 
such connections between them. A connection is com- 
pletely specified by its two ends which are called 
sockets. A network socket is itself mfiqucly specified by 
a host identifier and a socket identifier. The purpose of 
the socket identifier is to specify a process or group of 
processes within a host and a sockct relative to that 
process or process group. Thus, it is useful to think of a 
socket as hawing a three component "socket name" of 
the form H.P.N. H is the "host" component which 
identifies an ARPANET host, P is the "process" com- 
ponent which identifies a process group within H and N 
is the "process-locM" component which identifies a 
socket relative to P. In the sequel 
H. P. NaH. P,. N, 
is used to denote a connection between sockets 
H.P,.N, and H.P,.N, where -, indicates the direc- 
tion of information flow over the connection. 
For a connection to be established between two 
processes each must request that it be established. There 
are two common ways in which connections are es- 
tablished. In the first, the processes play symmetric 
roles. Each specifies, as part of a "request for connec- 
tion" (FC), the socket name at its end of the con- 
nection, the socket name at the remote end of the 
connection and the direction of information flow. If the 
two RFCs "match" the connection is established. This 
connection procedure requires a prior{ agreement upon 
the sockets to bc used for the connection. The second 
common connection procedure is used in situations in 
which one process wish'cs to provide some sort of service 
to other processes. The "serwing" process establishes 
a {teninq socket within its }lost which is receptive to 
RFCs from any other process in the network and then 
"listens" for connection attempts. The serving process 
uses facilities provided by its NCP to detect the occur- 
renee of a connection attempt and to determine its 
source. When such an attempt is made the serving 
process can choose to accept or reject it. This connec- 
tion procedure requires that only one socket name, 
that of the serving proccss's Listening socket, be known 
------------------------------<page break>-----------------------------
McROSS 23 
a pr/'. In the rcmaindcr of thin papcr 
CH.P.N-]L 
and 
are used to denote connections established in a listening 
state, 
The TENEX operatin 6 system 
TENEX  is a time sharing system for the DEC 
PDP-10 processor augmented with paging hardware 
developed at BBN. For purposes of this paper it is 
useful to describe TENEX in terms of tile virtual 
processor it implements for each logged-in user (i.e., 
user time sharing job). 
The instruction repctoire of the TENEX virtual 
proce&or includes the PDP-10 instruction set with the 
excep6.- of the direct I/O instructions. In addition, it 
inclu .... :-'.tructions which provide access to virtual 
processor capabilities implemented by the combination 
of the TENEX software and hardware 
The TENEX virtual processor permits a user job to 
ereate a tree-structured hierarchy of processes. Such 
processes have independent memory spaces and com- 
putational power. At different stages in its lifetime a 
single user job may include different numbers of pro- 
cossos in various states of activity. Several mechanisms 
for interprocess communication arc provided by the 
TENEX virtual machine. Processes can interact by 
sharing memory, by interrupts and by direct process 
control (e.g., one process stops, modifies and restarts 
another which is "inferior" to it in the hierarchy). 
A memory space is provided by the virtual processor 
which is independent of the system configuration of 
core memory. Each process hs a memory space of 
256K words which is divided'ifito 512 pages each of 
512 words. A process can specify read, write and execute 
protection for pages in its memory space ms it sees fit. 
The virtual machine includes a file system which 
provides a mechanism for storing information on and 
retrieving it from external devices attached to TENEX. 
Processes refer to files using symbolic names, part of 
which identifies the particular device on which the 
file resides. The instruction set of the virtual machine 
includes operations for data transfer to and from files 
which a process can execute without explicitly arrang- 
ing for buffering. 
The NCP resident in TENEX makes the ARPANET 
appear to TENEX processes as an I/0 device. The 
name of a "file" corresponding to a network connection 
includes the names of both tile local socket and the 
re. mote socket which define the connection. A proces.s 
requests TENEX to ('sta}.)lish l connection by attempt- 
ing to open an appropriately named "network" file. 
Tile open attempt succeeds and the con,cotton is es- 
tablished if and when another process issues a matching 
RFC. TENEX processes transmit and recciw informa- 
tion over network conncction.s by executing the normal 
file data transfer imstructions. 
ROSS 
ROSS is a programming systmn for modelling air 
traffic situationsY It includes facilities for creating and 
running simulation experiments involving air traffic in 
an experimenter-defined airspace. The system is cur- 
rently being used in a number of air traffic control re- 
search projects. 
To create a simulation experiment lhc experimenter 
uses ROSS language forms to write a "program" which 
defines the geography of an airspace, the wind profile 
for the airspace, aircraft flight characteristics and a set 
of "route procedures." A route procedure consists of a 
sequence of one or more "instructions" for monitoring 
or controlling the progress of an aircraft through the 
simulated airspace. Execution of a route procedure is 
the ROSS counterpart of pilot and/or controller actions. 
The "flight" of a simulated aircraft through the air- 
space is accomplished by the execution of a series of 
route procedures. ROSS includes "primitive" route 
procedures to "create" aircraft, "inject" them into and 
remove them from the simulated airspace ms well ms 
ones which causc aircraft to accelerate, turn, climb and 
&seen& 
By compiling his program the experimenter creates 
a simulator for traffe in the airspace he has defined. 
To perform a simulation experiment the experimenter 
runs his program. The simulated airspace remains 
empty until the program is supplied with input which 
inject aircraft into the airspace and control their flight 
through it Each input line the simulator receives is 
passed to an internal parsing mechanism which issues 
a call to an appropriate experimenter-defined or primi- 
tive route procedure. The program can accept input 
from an on-line terminal, a predefined "scenario" file, 
or both. Input lines from the scenario file are identical 
to ones from lhe on-line keyboard with the exception 
that scenario fife input lines include a time field which 
specifies the (simulated) time at which the program is 
to accept them. A user can manually "vector" aircraft 
through the airspace by supplying input at the on-line 
keyboard. 
A ROSS simulator can drive displays of the airspace 
------------------------------<page break>-----------------------------
28,t Spring Joint Computr Conference, 1.072 
and, in addition, can generate output which can 
written into files, typed on the on-hne keyboard 
sent back into the simulator inpul pttrser. 
TIlE McI[OSS PROGRAMMING SYSTEM 
The McROSS system provides the ability to define 
simulation experiments involving a number of airspaces 
or "simulation centers" which can be interconnected 
to form a simuhttor network. Adjacent centers in the 
simulator network are, connected to on('. another by way 
of the AR, PANET. The components of a simulator net- 
work may run ms user jobs distributed among different 
TENEXs or s di fierent user jobs on the same TENEX. 
(As of January 1972 the ARPANET included five 
TENEX hosts.) 
omputational responsibility for performing a multi- 
computer MeROSS simulation is truly distributed. 
For exomp[a, ms an aircraft flies from one airspace into 
an aUjacent one the responsibility for simulating its 
dynamic2 ,hilts from one computer to another. 
Goala 
The IX{cROSS System wa implemented to achieve 
the folloMng goals: 
1. Autonomy of parts: 
Individual components of a MeROSS network 
should be able to operate independently of one 
another (to the extent that each is independent 
of the others for traffic). Furthermore, no center 
should be able to cause another to malfunction. 
Autonomy of parts enables a multi--computer 
simulation to run when only some of its compo- 
nents are operational. FaiTtire of a component 
center in a multi-center simulation results in 
degradation of the total simulation rather than 
forced termination of it. A beneficial side effect 
of autonomy is that individual centers can be 
partially debugged without running the entire 
simulator network. 
2. Deferral of process/processor binding: 
The binding of centers in a McROSS net, work to 
host computers in the ARPANET should be de- 
ferred until run time. This goal can be stated in 
more general terms. The program for a dis- 
tributed computation defines a 1.ogieal configura- 
tion made up of abstract relations between the 
eomputation's parts. A given execution of the 
program is accomplished by a particular physical 
configuration of computers. The two configura.- 
lions, logical and physical, are by necessity re- 
lated. Itowever, the programmer should have 
the option of specifying them separately. By 
def(.rrmg process/processor binding [!e con- 
figurations can b: separately specified. As a 
result the programmer is free while composing 
his program to concentrate on the logical struc- 
ture he wants his program to define without 
concerning himself with details of the physical 
structure on which it is to be run. 
3. Capability for dynamic reeonfiguration: 
In the course of a simulation it should be pos- 
sible for adjacent centers to dynamically break 
and resstab[lab connections with one another. 
Furthermore, it should be possible for process/ 
processor binding to be changed during a simula- 
tion. That is, it should be possible to change the 
physical location of a center from one 
ARPANET host to another. The ability to dy- 
namically reeonfigure makes it possible to re- 
move an improperly operating center from the 
s!.mulator network and replace it with another at 
the same ARPANET host or at a different one. 
4. Decentralization of control: 
MeROSS is to be used as a tool for investigating 
distributed computation. Among the subjects to 
be studied are methods for controlling such com- 
putations. In particular, various techniques for 
distributing control responsibilities among the 
parts of a computation are to be experimentally 
investigated. It is important, therefore that 
operation of the McROSS system not require a 
central control mecha,fism for coordinating 
simulator networks. Stated somewhat differ- 
ently, the only components required for a 
MeROSS simulation should be simulation cen- 
ters defined by MeROSS programs. The realiza- 
tion of thi s goal, which makes experimentation 
with distributed control possible, should not 
preclude experimentation with centralized 
control. 
5. Remote monitoring capability: 
A MeROSS simulator network should provide 
parts through which its components are acces- 
sible to any ARPANET host. An appropriately 
programmed process rumting at any AR. PANET 
host should be able to "attach" to a component 
of a simulator network to monitor and control its 
operation. A remote monitoring process should 
be able to: 
a. obtain sufficient information to display [raffle 
in the airspace it is monitoring. 
b. serve as the on-line keyboard for the center 
it is monitoring; 
------------------------------<page break>-----------------------------
McRO$S 285 
c. "detach" from one. center and "attach" to 
another in the course of a simulation run. 
McROSS as seen by the user 
A McROSS simulator network is defined by a pro- 
gram composed of a "network geometry" sub-program 
and sub-programs corresponding to each of the centers 
in the network. 
The network geometry sub-program defines the logi- 
cal geometry for a simu}ator network. Conceptually, a 
network is composed of nodes and arcs. Nodes in a 
MeROSS network are simulation centers and ares are 
duplex connections between centers. Figure 1 shows a 
four node simulator network which could be used to 
simulate air traffic between Boston and New York. The 
following geometry sub-program defines that network: 
netcen BOSTRM, BOSCEN, NYCEN, 
NYTRM 
netcon BOSTRM, BOSCEN 
netcon BOSCEN, NYCEN 
netcon NYCEN, NYTRM 
The netcen statement declares that the network con- 
NYTRMi 
NCEN 
BOSCEN 
BOSTRM 
rains four nodes (Boston terminal c()ntrol, Boston vn 
route control, New York en rout(: cmtrol and Nvw 
York terminal centre}). The netcon stat.mcnts d('clare. 
the three arcs; netbegin and netend serve to brackv. t 
geometry declarations. 
In general, the sub-program for each center h four 
parts: 
 a route procedure module 
* a local geography module 
 a wind profile module 
.. an aircraft characteristics module. 
In addition to defining procedures followed by air- 
craft ms they fly through a center's airspace, lhe route 
procedure module includes routines specifying how the 
center interacts with its neighbors. Information ex- 
change between adjacent centers is accomplished by 
sending messages across the connection between. them. 
A center handles messages from neighboring centers by 
submitting them to its input parsing mechanism. Such 
messages are treated identically to input from its on-line 
console and scenario file. 
The ability of adjacent centers to iniract depends 
upon the state of the connection between them as each 
sees it from its end of the connection. A center may 
consider a connection to be in one of three states: 
1. uninitialized: 
the "physical location" of the neighbor is 
unknown; 
2. closed: 
the "physical location" of the neighbor is known 
but the connection is not capable of carrying 
messages (either because it has not yet been 
established or because it has been broken); 
3. open: 
the connection may be used for information ex- 
change with the neighbor. 
In the current implementation of McROSS the 
"physical location" of a neighbor includes both the 
ARPANET host the center is running on (e.g., BBN) 
and the identification of the user it is running under 
(e.g., Jones). 
McROSS provides the operations init, conn, dsconn 
and abort for changing the state of a connection. The 
effect these operations have on the end of a connection 
is illustrated by the state transition diagram of Figure 2. 
Consider the geometry for the Boston-New York 
simulation. Execution of 
Figure 1--A simulator network which could be treed to simulate 
air traffic between Boston and New York corm BOSTRM 
------------------------------<page break>-----------------------------
286 Spring Joint Computer Conference, 1972 
UNINITIALIZIED 
dconn 
Figure 2--Transition diagram for the state of the end of a 
connection showing the effect of the operations init, corm, 
dsconn and abort 
within the BOSCEN initiates an attempt to open a 
cenncct%r ";*h BOSTRM. The connection attempt 
succeeds ii a matching corm is executed by the 
BOSTRM eentor. The effect of executing 
dsconn NYCEN 
within the BOSCEN center simulator is to break the 
connection between the NYCEN and BOSCEN centers 
by forcing both ends of it into the closed state; abort 
works in an analogous manner. Execution of the init 
operation results in a center-user dialogue in which the 
human user is asked by the center program to specify 
the physical location of the neighbor. 
Two language primitives are provided for sending 
messages from one center to another. One takes a single 
operand, a message, which it sends to every neighbor 
whose connection is in the open state. The other takes 
two operands, a message and the nam.e of a neighboring 
center. If the connection to the center is open, the mes- 
sage is sent to the center; otherwise the operation has 
no effect. Because they are submitted to the input 
parsing mechanism care must be taken that messages 
sent to a neighbor are formatted correctly. 
MeROSS includes operations which can be used by 
a center to obtain information about the simulator 
network and its immediate neighbors. For example, 
there is a primitive which produces a list of all nodes in 
the network (i.e., all centers declared by the 7ctcc 
declaration); another one produces a list of all neigh- 
boring centers for which connections are in the open 
state. In addition, a center can examine the state of the 
connection to each of its mighbors individually. 
The local geo[raphy module defines the airspace of a 
center by specifying names and locations (z-y coordi- 
nates) of important geographic features such as naviga- 
tiomd Lids, obstructions and airports. tn ddition it 
includes a declarative statement which names the simu- 
lation center. For example, the geography module for 
the BOSTRM center would include the declaration 
atecon BOSTRM. 
This declaration has the effect of binding the identifier 
THISIS to the name BOSTRM. Thus in the BOSTRM 
center THISIS is bound to BOSTRM while in the 
NYTRM center it is bound to NYTRM. Route pro- 
ccdurcs which access the simulator center name can be 
rittcn in terms of THISIS to enable their use at any 
center in a simulator network. 
A properly authorized process at any ARPANET 
host can attach to a center in a McROSS simulator 
network and request output from it and direct input 
to it thereby monitoring and controlling its operation. 
McROSS center programs arc prepared to offer two 
'kinds of service to remote monitors: 
2 
broadcast service: 
Centers continuously broadcast certain informa- 
tion to monitors attached to them. Presently 
centers broadcast flight parameters of each air- 
craft in their air space (speed, heading, altitude, 
x-position, y-position, acceleration, aircraft id) 
and the (simulated) time. A remote monitor 
can use broadcast information to dhvc a display 
of traffic in a center's airspace or it can record 
it for later analysis. 
demand service: 
Each center is prepared to respond to certain 
specific requests from monitors. In the current 
implementation a monitor can request that a 
center: 
a. transmit its map of the airspace (which can 
bc used as background for displaying the 
center's air traffic); 
b. stop the continuous broadcast; 
c. resume the continuous broadcast; 
d. treat the monitor as its on-nc keyboard by 
directing keyboard output to the mofitor 
and accepting input from it; 
e. cease treating the monitor as its on-ne 
keyboard; 
f. break its connection with the monitor. 
The moIfitoring facility has proven useful both for 
debugging and for demorstration purposes. One diffi- 
culty a user faces in debugging a multi-center simula- 
tion is determining what is happening at centers sus- 
pected to be malfunctioning. A monitor, coustructed 
appropriately, can serve as a "graph/eal probe" and be 
------------------------------<page break>-----------------------------
McROSS 
287 
used to watch the operation of first one rampeet center 
and then another, For example, we have used such a 
mofitor t,o follow the trajectory of an aircraft aa it 
psscs through several centers. 
By enabling processes at. arbitrary ARPAN'ET sites 
to observe and control McROSS simulations, the 
monitoring facility provides a mechanism for using 
hardware and software features which are unique to 
various network installations. By using monitors which 
play an active role in his simulations a MeROSS user 
can experiment Mth different ways of partitioning 
computational and control responsibilities in air traffic 
situations. He could, for example, experiment with a 
monitor built to provide a weather advisory service for 
simulator centers. Such a monitor would presumably 
have access to an on-line weather data base. (A weather 
data base to be accessible through the ARPANET is 
currently being designed? e) To perform its service for a 
center the monitor would attach to the center, request- 
,:o t'i,, ..,2 -enter broadcast aircraft flight parameters 
to it and accept input lines from it. It would then 
"watch" the airspace of the center and send instructions 
to it, as necessary, to vector aircraft around severe 
weather. 
Unless he chooses to do so, the simulation program- 
mer need not concern himself with remote monitoring 
beyond specifying at simulation run time which centers 
in his network are to bc receptive to remote monit&s. 
Monitors themselves are not part of the McROSS 
system. McROSS merely provides a mechafism for re- 
mote monitoring. No effort has been made to provide 
linguistic features within the McROSS system to make 
it easy to write programs to do mmfitoring. 
THE McROSS IMPLEMENTATION 
Some interesting aspects of the MeROSS imple- 
mentation arc discussed in this section. The section 
focuses on strategy rather than detail. The result is a 
simplified but nonetheless accurate sketch of the 
implementation. 
The ROSS iraplcmcntation 
Implementation of hieROSS w accomplished by 
extending the existing ROSS simulation system. A 
ROSS simulation consists of initialization, simulation 
and termination phrases. The simulation ph.e is imple- 
mented ms a loop. Each pass through the loop repre- 
sents a "tick" of the clock which maintaiim simulation 
time. On each tick the simulator: 
1. parses and interprets input directed to it from 
CENTER 
SOCKTS 
H PA 'SA 
CENTER 
B 
Figure 3--Schematic of center-center connection between ad- 
jacent centers A and B. S,a, R,a, Saa and Ra, are ssigned at 
program translation time; H,, Ha, P, and Pa are determined 
at run time 
its scenario file and on-line console since the 
last tick; 
2. interprets the route procedure each aircraft is 
currently folloSng; 
3. advances each aircraft along its trajectory tak- 
ing into account the aircraft's speed, acceleration 
and heading and the wind profile of the airspace; 
4. directs output generated since the last tick to 
the appropriate devices; 
5. performs actions necessary to maintain the local 
display of its airspace: 
6. increments the simulated time. 
A ROSS simulation can be run either in a "real time" 
mode in which simulated time is locked to real time, 
or in a "hyper fast" mode in which the simulation pro- 
eeeds as fast as it can. 
Process/processor binding a? center-center connections 
Connections between pairs of simulator network 
centers are duplex. Each center-center connection is 
implemented by two ARPANET connections. IX{ore 
specifically, an open connection between centers A and 
B is realized by the two ARPANET connections (see 
Figure 3): 
Ha.Pa.S^,H.P.R^ 
H^. P^. R^,*--It . Pn. 
To establish such a center-center connection two pairs 
of matching RFCs must be issued by centers A and B. 
To issue the correct RFCs A must know Ht, P, 
trod Snx; similarly, B must know H^, P^, Rx and S^. 
------------------------------<page break>-----------------------------
288 Spring Joint Compulr Conferenc(', 1972 
The host (H) and proce.s.$ (P) components of the 
)cket names for a eenterenter crmncction cnnot [)e 
determined until run-time because proc('xs/procem)r 
binding is deferrr'd until then. Hnwever, the pr(}cexq- 
local c(mp(menls (I{ and S) of lhe socket names can be 
prc-sicd and, in ftml, Ihc eft,cs of the declarations 
in lhc nelwork geomeIry sub-program for a prlicular 
MeROSS network is Io do exactly that. 
The process loam eomponenls for lhe four socket 
names corresnding to a eenterenler conre'etlon are 
always the same whereaq the host and process comp 
nents may change from run to run or even 4thin the 
same run if either neighbor is involved in a dynamic 
reconfiguration. 
When a eenlcr's end of a centersenter connection is 
in the uninitialized state the host and proeea compo- 
nents of the eket names eoesponng to the remote 
end are unkno to it. To move its end of a connection 
from the unfifitialized state the center engages  a 
 aloe with the er requesting from him the physical 
location of the neighMr. After sueeefu[ly completing 
the aloe the center h sufficient iormation to 
sue the two FCs reqred of it to tabh the 
eoeetion. 
Center-monitor conneclior 
The connection between a center C and an artseiZed 
remote monitor M is realized by two ARPANET con- 
nections. One of them 
Hc. Pc. Sc,--*H ,. P, .R c 
is a "broadcast" connection used for continuously 
broadca.sting information to M. The other 
the. Pc. 
is a "request" connection maintainec't.by 12 in a listening 
state for 5{ to use to make requests of C. Each monitor 
attached to Chms its own broadcast connection but 
may share a request connection with other monitors. 
To make a request of 12, IX{ connects to the request 
socket, transmits its request over it and then closes the 
request connection, freeing it for use by other monitors. 
The action taken by C of course depen upon the re- 
quest. If the request were for the display map, C would 
transmit the map data over the broadcast connection 
to M. 
Before the RFCs required to establish a center- 
monitor connection between C and M can be issued 
C must know H, P and R,c and M must know 
He, Pc, Sc and t2. To obtain the required information, 
M and C engage in a connection protocol which is 
similar to the "initial connection protocol" developed 
by the ARPANET network working group? 
Elmh center gflling to service monitors maintains as 
an "attach" socket a send socket in a listening state 
(see Figure 4.It). The atlh eket for C could be 
denoted 
The proec local comportertl (A) of the name for at- 
tach sockets is the same for a}l centers and is "well- 
advertised." Therefore, if M knows the physical loca- 
tion of C it can issue an RFC for C's atth socket. 
The effect of such an RFC is to qtablh the connection 
(Figure 4.b) 
.Pc.AH.P.R 
Upon detecting an RFC for its atth socket, C notes 
H and P and transmits  and R over the connec- 
tion. Next both C and M break the connection and 
(o) 
CTR 
I II$1enlng 
(b) 
CENcTE R ' 
(c) 
CENcTE R . 
Hc' PC'T'M ---'*" HM. 
Hc'Pc'R J-- I liszenlng 
, ,MON;TORJ 
t,} 
- I listening 
 , N.M( 
. I listening 
I;TOR / 
Figure 4--Schematic of connection protocol exchange between 
center (2 amd monitor M 
------------------------------<page break>-----------------------------
McROSS 289 
issue the RFCs necessary to establish the broadcast 
connection (Figure 4.e) 
He. Pc ..Sc H . P. Rc 
where Rc= f(R), a pre-agreed upon function of 
C, if it has not done so previously for another monitor, 
sets up the listening connection 
the. Pc. R*-- 
and finally, reestablishes its attach connection so that 
other monitors can attach to it (Figure 4.d). Currently 
the process-local components for ARPANET socket 
names are numbers and f is taken to be 
f(x) =x+2. 
If R rather than f(R) were used for Rc a race 
condition would result when M and C attempt to estab- 
lish the broadcast connection. The race involves the 
crdc '; ..... hich the connection with socket H}.PM.RM 
woum oc ,1oscd and reopened by C and M. In particu- 
lar, the current TENEX NCP is such that an attempt 
by C to open the network file corresponding to its end 
of the (broadcast) connection 
Hc. Pc. Sc--H.P. R 
before M closes the network file corresponding to its 
end of the connection 
He. Pc. A--H ,. P ,. R , 
would fail. Use of f(R) for Rc avoids the race. A 
similar race condition, discovered in an carly version 
of the ARPANET initial connection protocol, 7 is 
avoided in the current protocol by the same technique? 
Process structure at McROSS centers 
A McROSS center is realized by a collection of co- 
operating, asynchronously evolving, sequential pro- 
cesses. The collection corresponds to a partitioning of 
the center's responsibilities into more or less indepen- 
dent sub-tasks. It includes: 
1. a process (SIM) to perform the ROSS functions; 
2. a process (CONN) for each center-center con- 
nection to establish and maintain the connection; 
and 
3. a monitor server process (MONSEt) to service 
remote monitors. 
The CONN process at center A corresponding to the 
center-center connection to center B is responsible for 
establishing ARPANET send and receive connections 
with B. After it. establishes the center-center connection 
( 
Figure 5--The process hierarchy which implemcnt a McROSS 
simulation center with n neighbors 
with B the CONN process maintains the connection. 
When messages from B arrive it passes them on to the 
SIM process for parsing. 
The job of the MONSER process at a center is 
twofold: to engage in an initial connection protocol ex- 
change with monitors attempting to attach to the 
center and to respond to requests made by attached 
monitors. 
The processes at a center exist in a hierarchy (see 
Figure 5). The hierarchical structure is less the result 
of any one process being more important than any 
other than it is a consequence of the TENEX con- 
straint that process groups be hierarehieally arranged. 
During initialization the SIM process ereares the 
MONSER and CONN processes. Thereafter, the pro- 
eesses evolve more or less independently. 
The process structure at each center helps achieve 
autonomy of parts. The CONN processes and the 
MONSER process serve to protect the SIM process by 
insulating it from direct interaction with other centers 
and remote mmfitors. 
Protocols 
The current implementation of the TENEX NCP 
is such that if a center were to unilaterally break a con- 
nection with a neighbor (by closing the two correspond- 
ing ARPANET connections) it could leave processes 
in the neighboring center in an irrecoverable state. For 
example, a process in the neighbor sending information 
across the connection at the time Jr'is broken would 
"feel" the close as if it had executed an illegal instruc- 
tion. To prevent such situations MeROSS centers en- 
------------------------------<page break>-----------------------------
290 Spring Joint Computer Conference, 1972 
gage in a prolocol exchange prior to breaking 
connections. 
The center-center prolocol is rehnivcly simple. To 
perform an abort or dsconn operation a center sends its 
neighbor a "request for abort" or "request for dis- 
connect" message and waits until it receives an ac- 
knowledgment before actually breaking lhe connection. 
Existence of the center-center protocol ha- two major 
implications. The first. is that a center-center connection 
has morn states than the three noted earlier. Tile addi- 
tional states arc transient ones which the connection 
passes through as the center and its neighbor advance 
through protocol exchanges initiated when one altempts 
to change the state of the connection. The transient 
states are invisible to the MeROSS user. Immediately 
after a dsconn (or abort) is initiated the SIM process 
treats subsequent operations involving the connection 
as if the connection were already in the dosed (or 
umn:';,;. ,ed) state. The second implication is that 
center-center connections carry "control" messages 
used in center-center protocol exchange in addition to 
"ordinary" messages intended for the reeeiver's parsing 
mechanism. The CONN process for each connection 
must be prepared to recognize and respond appropri- 
ately to both kinds of messages. 
McROSS centers expect remote monitors to observe 
a center-monitor protocol. In addition to the connec- 
tion and request procedures described earlier, the 
center-monitor protocol includes a disconnection pro- 
cedure much like the one used in the center-center 
protocol. 
Interprocess communication 
To perform their tasks the process. cs at a simulation 
center must interact occasionally. For example, the 
arrival of a message from a neighbor requires inter- 
action between the SIM and CONN processes. The 
CONN process receives the message and passes it onto 
the SIM process for parsing and interpretation. 
One way the processes interact is through shared 
memory. For example, the SIM and CONN processes 
have read and write access to a shared "connection 
table." There is an entry in the table for each center- 
center connection which includes the state of the con- 
nection, a semaphore  and other information relevent 
to the connection. Use of the table is coordimled by 
strict adherence to a convention which requires every 
"critical" access (every write access and certain read 
accesses) to an entry to be bracketed by P (lock) and 
V (unlock) operations on the entry's semaphore. 
The situation arising at a center when a neighbor 
attempts to break connection with the center is a 
typical one which requires interprocess communication. 
The CONN process corresponding to the center-center 
connection r(.ceives a "request for disconnect" mes,stge 
from tile neighbor. Center-center protocol requires the 
CONN process acknowledge the request so that, the 
neighbor can break the connection. The purpose of the 
protocol exchange is to warn the center that the 
neetion is about to be broken and that it should no 
longer attempt to use it. Therefore before it acknowl- 
edges the neighbor's request it is important that the 
CONN process communicate this information to the 
other processes at its center. The CONN process does 
this by the following sequence of actions: 
P (CONNECTION SEMAPHORE); 
set connection-state to "not open"; 
V(CONNECTION SEMAPHORE); 
acknowledge neighbor's request 
As long as processes at the center perform the fol]oqng 
sequence of actions to send over center-center connec- 
tions there is no danger of sending after the connection 
has been dosed: 
P(CONNECTION SEMAPHORE); 
if connection-state = open 
then send 
else abort the send; 
V (CONNECTION SEMAPHORE) 
Stated somewhat differently, sending over a center- 
center connection should be regarded as an operation 
which involves a "critical" read access of the corre- 
sponding connection table cntryo 
In addition to memory sharing, direct process control 
is used as a mechanism for interprocess communication 
in the McROSS system. Because of its superior position 
in the process hierarchy the SIM process can exert 
direct control over the olhcr processes. A few situations 
occur in which it does so. For example, when a ccntcr- 
center connection has been closed or aborted (via 
dsconn or abort) the SIM process forces the correspond- 
ing CONN process to halt. If and when an at.tempt is 
initiated to reestablish the connection (via conn) 
SIM restarts it. 
SOME OPEN QUESTIONS 
This section briefly discusses questions representa- 
tive of ones which have arisen in tile course of using 
the McROSS system. The questions hart,  been resolved 
to tile extent thai useful simulations can be performed 
using McROSS. However, none }us been resolved in a 
------------------------------<page break>-----------------------------
McROSS 291 
totally satisfactory manner. The inten! of this section 
is to leave the reader with an appreciation for the issu('s 
raised by these questions; a thorough discosion of 
them is well beyond the scope of th par. 
Synchroni2atfon 
Simulated time is important in the operation of the 
McROSS system. In particular, whenever an inter- 
ation between adjacent centers occurs it is important 
that the clocks kept by the centers show approximately 
the same time. Time synchronization is a specific ex- 
ample of the general problem of control in distributed 
computation. It is compounded by tile fact that centers 
can start up and shut down independently of one 
another. A centralized approach to synchronization 
has been used with success in MeROSS simulations. 
In it, one center acts as a synchronizer for an entire 
simulator network. When a center starts up it connects 
to the synchronizer and receives a synchronization 
message from it. Thereafter, to stay in syneh with 
c9,ar 2nters in the network, the center makes use of 
the real time clock in the computer it runs on. A dis- 
tributed approach to synchronization which does not 
require a synchronizing center is under eonsideratiom 
Locally unknown names 
Names that axe well defined within a simulator net- 
work as a whole axe not necessarily defined at every 
node in the network. How should references to such 
names occurring within centers in which they are not 
defined be handled? For a specific example in which 
such a reference is reasonable, reconsider the four node 
network for simulating Bosto_n.-New York traffic..A 
user controlling the simulator fo Boston Terminal who 
is manually vectoring an aircraft leaving Logan airport 
might reasonably issue the clearance 
fly (V205, PAWLING) 
which specifies that the aircraft is to follow Victor Air- 
way 205 to Pawling. Assume that V205 is defined 
within the geography modules for BOSTRM, BOSCEN 
and NYCEN and the PAWLtNG is defined within 
NYCEN but not within BOSTI.M or BOSCEN. The 
BOSTRM center can't fly the aircraft to Pawliag be- 
cause Pawling is not defined within its airspace. Ideally 
it should fly the aircraft along V205 to the boundary 
of the BOSCEN airspace and then hand it. off to the 
BOSCEN simulator. Certainly it should be able to do 
better than report an error and abort the route pro- 
cedure. TeeMfiques for handling referchines to locally 
unknown names in certain limited contexts are being 
investigated. 11owever, the general problem of handling 
such references is an open question. 
Pro, ram rcsiderxe 
Where should the program (route procedures) re- 
quired to fly an aircraft through several simulator 
centers reside? Should the program be associated with 
the aircraft and passed with it from center to center or 
should parts of the program be distributed among the 
relevant centers? The approach currently used in 
MeROSS simulations is to distribute the program and 
pass only the aircraft and its flight parameters from 
center to center. 
Interruption and resumption of route procedures 
Aircraft frequently interrupt their flight plans tem- 
porarily in order to avoid severe weather or heavy 
traffic. The simulation analogy to a flight plan is the 
route procedure. How should a center handle interrup- 
tion and subsequent resumption of route procedures? 
Interrupting the execution of a route procedure in 
order to follow another one is not difficult. The diffi- 
culty arises in determining how to appropriately resume 
the interrupted procedure. In general, the point of in- 
terruption is inappropriate as a resumption point. A 
considerable amount of (simulated) time can elapse 
between interruption and resumption during which the 
flight parameters (position, speed, altitude and head- 
ing) of the aircraft can change significantly. Theyefore, 
the usual programming technique of saving the "state" 
when an interrupt occurs and restoring it after the 
interrupt has been handled is inadequate. The inter- 
ruption/resumption problem is made more complex by 
the possibility that between interruption and resump- 
tion the aircraft may fly out of the airspace of one 
center and into the airspace of another. The current 
MeROSS implementation is not prepared to handle 
interruption and subsequent resumption of route 
procedures. 
Error handling tccbmqucs for distributed systems 
The question of how to handle rror situations in a 
distributed computational system is a challenging one. 
In McROSS considerable attention has been given to 
making nodes in a simulator network autonomous. The 
strategy for handling errors is o try to achieve a 
"local" error recovery whr,reby a node attempts to pre- 
serve its autonomy. As a result, while the actions it 
------------------------------<page break>-----------------------------
29.2 Spring Joint Comput.t:r Conference, 19'72 
Inkes are hmtlly ptimn! in the. svns(' ltmt its cominued 
ol)(.ration is insur(.d, th('y may b(' subI)timd in th(' 
mor' gl()bil cont (.xt ()f th(. ('nt it(. simuhtt ion m't w()rk. 
Errors oceurri]g in in',cr-n(d(. m(,ssag('s at(. simply 
}mnd[(.d in th(' currm)t Mct{()SS imp}(.nwnlati(m. 
call from ltll earlier s(.ction tlmt int(.r-nod(' mr'sstg(,s 
are submitted to the parsing mechanism of the destina- 
tion node. When a node receives a message which is 
syntacticidly incorrect or semantically meaningless 
(to it) from a neighbor, it r(,pr)rts the ('rror on its 
on-line keyboard, sends a message to the neighbor eaus- 
ing the error to be reported on the neighbor's on-line 
keyboard, and ignores the message. This proc('durc is 
locally satisfactory in the sense that it guarantees that 
messages which are nol wvll-formvd cannot ctus(' 
node to malfunction. However, if lhe incorrect message 
from the neighbor is one critical to the oulcome of the 
simulation, this procedure is not globally acceptable. 
Ideally, upon detecting an error in a message, the node 
should enge in a dialogue with its neighbor in an 
attempt, to resolve the error. The difficulty in imple- 
mexting this strategy is that it is frequently unclear 
what should be done to resolve an error. Often the 
cause h been mked by the time the error is detected. 
While the simple techniques used in MeROSS for 
eor handling have proven adequate, it is clear that 
more effective tcchques can be developed. 
CONCLUDING REMARKS 
The results of the work reported in this paper are 
pileable in two are. 
One area is research in air traffic control. Researchers 
can use the McROSS system to conduct simulation 
studies preliminary to the design of an automated 
multi-component air traffic cont*ol. system. For ex- 
ample, McROSS could be used to evaluate various 
ways of partitimfing responsibility among components 
of such a system. Or, it could be used to compare differ- 
ent strategies for automated scheduling and control of 
aircraft. Because it exhibits autonomy of parts and the 
ability to dynamically reconfigurc, it could be used to 
experimentally study the behavior of failure bandling 
techniques for a multi-center system under various air 
traffic loads. 
The other area is the design and implementation of 
distributed computation systems. The results in this 
aret are incomplete and tentative cousisting primarily 
of insights and attitudes developed from the experience 
of building and using a distributed computation system. 
These arc summarized by reviewing the greeks ftr tbc 
McROSS system in terms of problems they posed and 
techniques useful in realizing them. 
Of the five goals, autonomy of parts and dcferral of 
process/processor binding were tile most significant in 
tvrms of vffort rcrluir.d to lchi(.v(. lhem md influence 
on the appearance of the system to users. (liven their 
r('tlizali(m, the other thr('c grmls (the ability to dy- 
mtmicnlly rvconfigur<'. it slmuhttor network, d.c('ntrtdi- 
zalion of control and ports for monitoring) were rela- 
tively emsy to achieve. 
The strategy of implementing parts of the distributed 
computation by process groups rather than sohtary 
processes contributed significantly to achieving au- 
tonomy of parts. The. multi-process implementation 
made it possible to dedicate certain processes at a node 
to maintaining an interface with other nodes and to 
dedicate olher processes to performing functions crucial 
to the node's existence. In tddition to imulating vital 
inlernal node functions from lhe actions of other nodes, 
the functional modularity resulting from multi-process 
nodes had the effect of reducing the eomplety of the 
implementation: each individual proee being con- 
siderably less complex than an entire node. The multi- 
process capabihty which the TENEX operating system 
suprts for each user job w invaluable in envying 
out the multi-proee strategy. It is unfounate that 
few operating syste allow em to create and main- 
tain process structures. 
Equally eful in realizing autonomy w the esta 
lishment of and strict adherence to protocols for pa- 
pa intertiom. A center can .exact momm and 
adjacent eente which are funetimfing properly to 
sere protocol and can therefore interpret a breh of 
protocol  a warifing that the offender may be 
functimfing. A comequenee of the multi-proc imple- 
mentation of nodes is that interproems commication 
occm Mthin MeROSS at two levels: inter-node and 
intra-node. Use of a protocol for intra-node intertiom 
helps ime that internal node data bes always 
eately reflect the eontion of the node's interfe 
Mth other nodes. A rueful implementation re w to 
reject any teehfique whose suee depended upon the 
order in which events in different centera or in fferent 
processes within the same center occ. 
The major problem in implementing defemed proeel/ 
proeeor binng w prong a way for pas of the 
computation to deterne the location of 1ocMly 
jent pts at run time. The solution ed in the 
current MeROSS implementation, wch reqr mn 
timc interaction with the er, is not totally satisfy- 
tory. A more sathfactory alternative ght be for ch 
pa to enge in a network-Mde search for loeally 
adjacent pts. 
We exB'et to see a trend toward distributed multi- 
computer systmms in the fute. By its etenee 
McROS8 demonstrates that the eomtruction of such 
syste  cently legible. 
------------------------------<page break>-----------------------------
McROSS 293 
ACKNOWLEDGMENT 
The McROSS system grew from an idea proposed by 
Dr. W. R. Sutherland of BBN; we gratefully acknowl- 
edge his guidance and enthusiasm. 
The realization of the current MeROSS implementa- 
tion is the result of building upon the work of others, 
most significantly the designers and implementers of 
the ARPA computer network and of the TENEX 
operating system. 
REFERENCES 
L G ROBERTS B D WESSLER 
Computer network develoFment to achieve resource sharinq 
Proceedings of AFIPS SJCC 1970 
W R SUTHERLAND T H MYER E L THOMAS 
D A HENDERSON 
A route oriented simulation system for air traffu: conlrol 
studies 
Proceedings of the Fifth Conference on Applications of 
Simulation Deeember 8-10 1971 
F E HEART R E KAHN S M ORNSTEIN 
W R CROWTHER D C WALDEN 
The interface messa9e processor for the ARPA network 
Proceeding of AFIPS SJCG 1970 
4 S CARR S CROCKER V CERF 
HOST.HOST protocol in the ARPA computer network 
Proceedings of AFIPS SJCC I970 
5 D G BOBROW J D BURCIIFIEL D L MURPHY 
R S TOMLINSON 
TENEX, A pacd time sharinq system for the PDP-IO 
Paper presented at tho Third ACM Symposium on 
Operating System Princip}es October 18-20 1971 
published in Communications of the ACM March 1972 
6 ARPA network current network protocols 
Augtrot 1971 Avai}able from the Network Information 
Center as NIC $7104 at Stanford Research Institute 
Menlo Park California 94025 
7 W NAYLOR J WONG C KLINE J POSTEL 
Rqmrding proffered official ICP 
Unpublished memo availab}e from Network 
Information Center NIC 6728, 1971 
8 A SHOSHANI 
A solution to te race condition in te ICP 
Unpublished memo available from the Network Information 
Center NIC $6772 1971 
9 E W DIJKSTRA 
Cooperatin satuential processes 
Appe&r in Programming Languages edited by F Genuys 
Academic Press New York 1968. 'Also published as Peport 
EWDI23 Dept of Mathematica Technological Univeity 
Eindhoven The Netherlands 1965 
10 D STERN 
Weather data 
Unpublished memo available from Network Information 
Center NIC $7692 1971 
------------------------------<page break>-----------------------------
Oeographlc 
Features 
Weather ! 
^lrcraft 
Characteristics 
Route 
Procedures 
TTY 
AA123 spd 
(480.0 
Simulator for 
Airspace 
TTY 
Ispl 
LPT 
Description of McROSS Simulator,Network: 
netbegin 
CLEVCEN B 0 ST R.)' 
.BOSCEN 
(,,j) NYTRM 
netcen NYTRM, BOSTRM, NYCEN 
BOSCEN, CLEVCEN; 
netcon (NYTRM, NYCEN); 
netcon (NYCEN, BOSCEN); 
netcon ( CLEVCEN, NYCEN ); 
netcon (CLEVCEN, BOSCEN); 
netcon (BOSTRM, BOSCEN); 
netend 
------------------------------<page break>-----------------------------
GDM 
LEROY 
PUT 
WHT 
\ 
ACTON \ 
EAl!l 
WESTON 
JiLLIS NE7B 
A/I)4 244i 
T 
WICH 
'ERE 
PVD 
TURNER 
Components of Mc ROSS 
 ROSS 
 TENEX Operating System 
,ARPANET 
Syslem 
------------------------------<page break>-----------------------------
BOSCEN and BOSTRM Establish Connection by: 
(at BOSCEN) (at BOSTRM) 
Init (BOSTRM, BBN, SMITH); Init (BOSCEN, UTAH-10, JONES); 
conn (BOSTRM); conn (BOSCEN); 
,Configuration During a Typical McROSS Simulation Run 
CLEVCEN BOSTRM 
SANTA MONICA',,,,.,, ./'""" CAMBRIDGE) 
, / "(-y 8oscE. 
/ .,,,,,,"k.- ( S R I - A R C _ ' 
.,c. / / .LO LO 
( UTAH-[O ' 
S 
NYTRM 
(BBNB 
CAMBRIDGE)  MONITORING PROCESS 
(LL-TX-2 
LEXINGTON) 
------------------------------<page break>-----------------------------
Breaki__n_ng and Re-establishing Connections 
A performs: A performs: 
ds con n ( B ) con n ( B ) 
------------------------------<page break>-----------------------------
Actions following dsconn (B)by Center A 
( Center A ) 
( Center B ) 
CONN(B).--- NOT OPEN 
send 
Simulate 
'RFDCN' 
awai! 'AKDCN'.. 
CONNIB }---CLOSED 
break network 
connection to B 
.r ecv 'RFDCN' 
I 
CONN( A )--C LOS ED 
I 
return 'AKDCN' 
I 
break network 
connection to A 
I 
------------------------------<page break>-----------------------------
Dynomic Reconfiqurolion by_ Cenler A 
A perfor ms: 
move ( H' U ) 
(at H') 
/ 
Simulate 
Center A 
I 
get self 
from H 
I 
get F _. 
from H 
attempt to 
re-est ablls h 
connection 
with B 
I 
CONN(B ).-0 PE 
(at  ) 
move self 
to H' 
I 
move Ft 
to H' 
I 
log out 
Center B 
break network 
connection to 
A at H 
attempt to Slmu 
r e-establ Is h 
connection 
with A at H' 
I 
CO N N (A).---O P E N 
ate 
------------------------------<page break>-----------------------------
(at H') 
create.. 
ob 
get self 
from H 
I 
Actions following move (H' U) by Center A 
Center A 
(at H) 
Io9 into 
Simulate 
H'as U 
CONN(B)"-'-NOT OPEN 
send "RFMOV H' U" 
Simulate await "A KMOV".- 
move self 
tO H' 
I 
Center B 
 .recv 'RFMOV' 
t 
CONN( A)-CLOSED 
I 
return 'AKMOV' 
break network 
connection to 
A at H 
I 
------------------------------<page break>-----------------------------
Extensions of packet communication technology 
to a hand held personal terminal' 
by LAWRENCE G. I{OBERTS 
A doancod Rear, arch Projects A cncy 
Arlington, Virgiaia 
INTRODUCTION 
Electronic communications technology has developed 
historically almost completely within what might be 
called the circuit switching domain. Not until the last 
decade has the other badsic mode of communication, 
packet switching, become competitive. Thus, as a tech- 
nology, packet communication hs only begun to be 
explored. Circuit switching can be defined in the broad 
sonse as the tcchniqu(: of establishing a complete path 
between two parties for as long as they wish to com- 
municate, whereas packet switching is where the com- 
munication is broken up into small messages or packets, 
attaching to each packet of information its source and 
destinatic-n and sending each of these packets off inde- 
pendently and asynehronously to find its way to the 
destination. In circuit switching all eonfiiet and alloca- 
tions of resources must be made before the circuit can 
be cstabl/shcd thereby permitting the traffic to flow 
with no conflicts. In packet switching there is no dedi- 
cation of resources and conflict resolution occurs during 
the actual flow perhaps resulting in somewhat uneven 
delays being encountered by the traffic. Clearly, without 
the speed and capability of modern computers, circuit 
sMtching represented a cheaper and more effective 
way to handle communications. For radio frequency 
assignment and telephone exchanges the resource allo- 
cation decisions could bc made infrequently enough 
that manual techniques wcrc oginally sufficient. Also, 
since voice was the main information being communi- 
cated, the traffic statistics wcrc sufficiently compatible 
with this approach to make it quite economic for the 
period. Packet switching of a kind, the telegram, per- 
sisted throughout this period but duc to the high cost 
of switching and the limited demand for fast message 
traffic never attracted much attention. 
For almost a century circuit switching dominated 
the communications field and thus dominated the de- 
velopment of eommmfieations theory and technology. 
Now, within the last decade or less, the advances in 
digital computers and electronics have, in many cases, 
reversed the economic balance between circuit and 
packet communication technology. Perhaps the best 
proof of this is the economy of the ARPA Network -s 
for country-wide computer to computer communica- 
tion, but many other examples arc beginning to appear 
such as the University of Hawaii's ALOHA System  
utilizing packet radio transmission for console com- 
munications and the experiments with digital loops for 
local distribution. However, most of the experiments 
with packet communications have been' undertaken by 
computer scientists, and it is not even generally recog- 
nized yet in the communications field that a revolution 
is taking place. Even where the knowledge of one of 
these experiments has penetrated the communications 
field, it is generally written off as a possibly useful new 
twist in communications util/zation, and not recognized 
as a very different technology requiring a whole new 
body of theory. Throughout the development of the 
ARPA Network, communication engineers compared it 
with conventional circuit switched systems but, per- 
haps unconsciously, used rules of thumb, statistics and 
experience applicable only to circuit s5tched systems 
as a basis for comparison. A century of experience and 
traxtition is not easy to ignore and in fact should not be 
ignored, only it should be properly classified and segre- 
gated as resulting from a different technology. 
Packet communication technology is only beginning 
to be explored but already it is clear that the design of 
all forms of communications channels and systems 
should be rcthought. As an example of the 'kind of 
difference packet communications can make in a per- 
haps unexpected area, the design of a personal terminal 
will be explored in some detail. Although such a ter- 
minal has never bccn built, it is most hkcly completely 
feasible to build and would provide many unique 
m:tvantagcs. 
295 
------------------------------<page break>-----------------------------
296 Spring Joint Computer Conference, 1972 
tlAND HELD PEIrLS()NAL TERMINAL 
J,_x't. us start with the goal of providing ratch individual 
with a pocket-sized, }figlily reliMHe and s(;cur(' com- 
munications device which would permit him to send 
and receive messages to other individuals or to co- 
puters. [x:aving the consideration of design alternat. iv(s 
muntil the end, a device fulfilling these objectives is as 
follows: 
Output 
Text. or graphics displayed on a 2.S"XI" phsma 
panel with S0 dots per inch resolution. The screen, 
divided into 7 X 10 dot rectangles, using ,5 X 7 characters 
would hold 8 lines of 32 characters each for a total of 
256 characters. Text this size is aimost the same size as 
typewriter print, except that the Lines are closer to- 
gether. The plasma panel has internal storage and is 
digitally addressed to write or erase a point. 
Input 
Five capacity or strcss sensitive buttons used by thc 
five fingers of one hand simultaneously to indicate one 
of 31 characters. This five finger keyboard technique 
was developed by Doug Englcbart at SRI s to permit 
users to type Mth only onc hand while working on a 
display console. Recently the keyboard has become 
fairly widcly used at SRI duc to its great convenience. 
Training time for a new user is evidently less than a 
day and speeds of 30 words per minute can bc achieved.  
Although somewhat slower than a good typist ( 
speed) the speed is clearly sufficicnt for a terminal 
devicc even at 10 words/minutc.-  . 
Transmission 
Each input character will be transmitted to a central 
controller station using the random access radio trans- 
mission techlfiqucs developed at the University of 
Hawaii.' The 5 bit character is embodied in  64 bit 
packet containing: 
30 bits--Terminal Identification Number 
8 bits--Character plus alternation bit, or Count 
2 bits--Type of packet (CHAR, ACK, CNT, 
ERR, ST ERR) 
24 bits--CycLic Sum Check 
64 bits 
All terminals transmit their packets indel)endently trod 
tmynchronously on a single frequency and the receiver 
at the central controllr.r mer('ly listens for a complete 
packcl which has  corr('ct sum ch('ck. If two t(.rmhmls' 
transmissions overlap the sum check will be wrong, and 
the terminals will retransmit when they find th('y doWt 
rvceiv('. m acknowledgment. Retransmi.,sion time-out 
intervals are randomizod between the terminMs to 
avoid recurrence of the problem Upon r(.ceipt of a good 
packet, the central station transmits a display-ac- 
knowledgment packet back to the terminal on a second 
frequency. This 144 bit packt:t contMns a 70 bit display 
rter field and an 8 bit position on the screen. The dis- 
play rter is a 7 X 1.0 dot aay for the character sent 
in and the position includes 3 bi for vertical by 5 bits 
for horizontal. Current position information for each 
active user is kept by the ce. ntral station by user ID in 
a hash table. Thus, the individual terminal needs no 
character generation 1oc, position advancement logic, 
or any other loeM verification of the input since the 
response from the centrM station both acknowledges the 
character and displays it in an input text line at the top 
of the display. If a character display-acknowledgment 
is somehow lost in transmission the terminM will con- 
tinue to time-out and rctransmit the character. The 
central station must somehow differentiate this from 
g new character. This is achieved by an alternation 
bit . in the tcrminM's packet which is complemented 
for each new character. On a repeat the bit is the same 
as preGously and the central station just retransmits 
the same character and position again. When a pre- 
arranged terminating character is sent the central 
station examines the message and takes an appropriate 
action. Considerable flexibility exists here, and opera- 
tional modes could be established. However, the first 
message of a sequence should contain a destination as 
the first item. This might bc the ID of anothv. r terminal 
in the same area, it might be the address of a service 
computer or it might be the ID of another terminal 
hMfway around the world. In the latter two cases, a 
more global network such as the ARPA Network comes 
into play. It would be perfectly feasible for a message 
to another terminal to be sent to a central or area-coded 
directory computer to locate the particular control 
station the other terminal was near. Note that the loca- 
tion of neither man was given to the other, only the 
message and the ID of the sender. (Based on ARPA 
Ne. twork cost estimates and international satellite tariff 
trends, such a message exchange should cost less than 
0.1 cents, independent of distance.) 
Reception 
At any time when a message d('stined for a terminal 
arrives tit the central control station, a transision to 
------------------------------<page break>-----------------------------
Extensions of Packet Communication Technology 297 
the terminal may begin, character by character, each 
in its own 144 bit, packet as follows: 
30 bits--Terminal Identification Number 
70 bits--7 X 10 dot pattern, character display 
8 bits--position of character 
1 bit --alternation bit 
1 bit --broadcast mode 
3 bits--Message Type (Response, initial, 
normal) 
8 bits--Characters Left in message 
24 bits--Cyclic Sum Check 
144 bits 
 The terminal must always be checking all transmission 
to detect those with its ID and a correct sum check. 
When one occurs which is not a "response" to an input 
character, a message is being sent. The first character 
of a message is marked type "initial," and has the 
count of the remaining characters. Each character is 
displayed where the central station placed it. Following 
the "initial" character "normal" characters are checked 
to make sure the count only decreases by one each time. 
After the character with count zero, an acknowledg- 
ment type packet is sent by the terminal. If this is lost 
(as it may be due to conflicts) the central control will 
retransmit the final character over again without eom- 
plementing the alternation bit until it is acknowledged 
(or it determines the station is dead). If a count is 
skipped the terminal sends a CNT ERR message with 
the count of the character expected. The transmitter 
then starts over at that count. If a "normal" type char- 
ae[er is received before an "initial" type a ST ERR 
message is sent and the. message is restarted. A broad- 
case bit is included which overrides the ID cheek for 
general messages. 
Security 
Since all transmissions are digital, encryption is pos- 
sible and would be important no matter what the appli- 
cation, military or civilian. Most private uses such as 
personal name files, income-expense records, family 
conversations, etc., would be far more sensitive than 
current computer console use. 
Bandwidth 
Personal terminals for occmional use for message ex- 
change, maintaining personal files, querying computer 
data bes for reference data, etc., would not lead to 
very heavy use, probably no more than two query- 
responses per hour. The query we might estimate ai 64 
characters in length and the respohse ,t 256. (Clearly 
256 character response could also consist of an 80X 
224 point graphic display since each charactcr is sent as 
a full 7X 10 raster.) The average bandwidth consumed 
by each terminal is therefore 2.3 bits/second trans- 
mitted tnd 25.6 bits/second received. The random ac- 
cess technique used for transmiasion requires the chan- 
nel bandwidth to be six times the average bandwidth 
actually utilized in order to resolve all conflicts prop- 
erly. Thus, the terminal transmission bandwidth con- 
sumption is 14 bits/second, still less than the receiver 
bandwidth needed. Thus, the central control station's 
transmitter bandwidth is the limiting factor assuming 
equal bandwidths on both transmitter and receiver. If 
a 50KHz bandwidth is used for each and modulated 
at 50K bits/see, then a total of 2000 terminals can be 
accommodated. Of course this number depends on the 
activity factor. At one interaction every two minutes a 
data rate equal to average time shared console use is 
obtained and even at this activity 130 terminals can be 
supported, more than most time-sharing systems can 
support. With 50 KB channels, the time required to 
a'ite 256 characters is about one second. Lower band- 
widths require increased time, thus, 10KB (5 sec write 
time) would be the lowest bandwidth reasonable. Even 
at this bandwidth, with the estimated 2 interactions 
per hour, 400 terminals could be supported. 
COMPARISON 
Comparing the effect of the packet technology with 
the same terminal operating with preassigned Fre- 
quency or Time Division Multiplexed channels (ignor- 
ing the losses due to TDM sync bits or FDM guard 
bands) the circuit oriented terminal would require a 
40 bit/see transmit channel and a 4KB receive channel 
if a 5 sec rite time is to be achieved. For 400 terminals 
with a 5 scc write time, the circuit method would re- 
quire a total of ].( Megabits/see bandwidth whereas the 
packet method only requires 20 Kilobits/see band- 
width. Thus, the circuit technology requires a factor of 
80 more bandwidth than the packet technique. Of 
course, the circuit mode terminals could interact more 
often within the same bandwidth right up to continual 
rcritc of the display every five see, but you would 
have to massively reshape the user statistics to suit the 
technology. 
Another possibility, to design the terminal so that it 
performed more effectively in a circuit oriented mode, 
would bc to put character generation logic and position 
logic in the terminal. This would considerably increase 
the cost of the terminal, which originall), had very little 
logic except shift registers. The result of adding this 
logic, however, is to reduce the bandwidth by a factor 
------------------------------<page break>-----------------------------
298 Spring Joint Computer Conference, 1972 
of 10to .16MBorstilI 8 tim(,s the packet technique. 
The am{' logic would h.lp r'duc t}.' packel size' but, 
in order to maintain the gmphie out.put capability and 
gross simplicity, it does not se{'m to pay. 
CONCLUSION 
As can be seen from the example, packet technology is 
far superior to circuit technology, even on the simplest 
radio transmixion level, so long as the ratio of peak 
bndwidth to average bandwidth is large.. Most likely, 
the only femsible way to design a useful and economi- 
cally att. raetivc parsohM terminal is through some 
of packet communication technology. Otherwise one 
restricted to uselessly small numbers of terminals on 
one channel. This result may also apply to many other 
important developments, only to bc discovered as the 
technology of packet communication is further 
developed. 
REFEREN t.,ES 
1 L G ROBERTS B D WESSLER 
Computt.'r octwork development to achicvc rc*ourcc sharir 
SJCC 1:170 
2 F E IIEAII. T I. E KAIIN S M ORNSTEIN 
W II CROWTH'EI{. D C WALDEN 
The intcrfacc rneasac processor for thc ARPA nelwork 
SJCC 1970 
3 L KI,EINROCK 
A rmt!fiic and simulalon mtthod. in computer twork dc. 
,CC 1970 
4 I[ FRANK I T FRISC[[ W CIIOU 
7'opotoical oi&ratio in the dci of the ARPA 
compldt t.lwork 
SJCC I970 
5 S CARl[ S CllOCKIqll V CEIIF 
tIOS7'-tlOST communecalgon protocol in lh. A RPA tclwork 
CC 970 
6.I, G I(OBEI[TS 
A forward look 
SignM Vol XXV No I2 pp 77-8I Augnst 1971 
7 N ABRAMSON 
THE ALOHA Syat'm--Ath* alt*natiuc for computer 
communicaliom 
AFIPS Conference Proceedings Vol 37 pp 281-285 
November 1970 
8 D C ENGELBAI[T W K ENGI,ISI[ 
A rccarch cml for aumci human icllcct 
AFIPS Conference Proceeding. Vol 33 p 397 1968 
9 D C ENGELBAI[T 
Stanford l[earch Institute Menlo Park CMi[ (PermnM 
communication) 
10 W C LYNCH 
Rcliabl full-dupt file tramisMon ou f, duplcz 
tclnc lim 
Communications of the ACM Vol I1 No 6 pp 407410 
June 1968 
11 K A BARTLETT I[ A SCANTLEBURY 
P T WILKINSON 
A tc on rcliablc full-duplcz tramfsaion ou fuplez 
link8 
Communications of the ACM Vol 12 No 5 pp 26261 
May 1969 
------------------------------<page break>-----------------------------
COMMUNICatiONS 
CHANNELS 
tECHNOLOGY 
PACKETS 
OEND-tO-END CIRCUIT 
OINFrEQUENt DECISIONS 
ADDRESSED MESSAGE 
 DYNAMIC RESOURCE 
ALLOCATION 
TELEPHONE (1876) 
FACSIMILE (I24) 
AND DESCENDANTS (1960'S) 
^.P^NET (,969) 
ALO" NET (1969) 
LGR/WHATWILL THE DISPLAY HOLD?/ 
 THE PLASMA PANEL WILL DISPLAY 
8 LINES OF 32 CHARACTERS FDR A 
TOTAL OF 256. EACH CHARACTER IS 
7x10RASTER UNITS' ALTERNATIVELY 
THE 80x224 RASTER CO..LtLD BE USED 
FOR GRAPHICS OUTPUT. (LGR). 
HAND HELD PERSONAL TERMINAL 
------------------------------<page break>-----------------------------
BANDWIDTH REQUIREMENTS FOR IOOO TERMINALS 
TOT AL 
BANDWIDTH 
lOMB 
IMB 
1OOKB 
1OKB 
 H AN I SEC 
- NEL 
o1/  o sc TEM 
PACKET . 
$YS'1- 
I SEC REWRITE 
USEFUL RANGE i MESSAGES/HOUR 
I [ 
lO 1o 1oo 
------------------------------<page break>-----------------------------
PERFORMANCE WITH -< 5 $EC DISPLAY REWRITE 
FOR A RATE OF 2 MESSAGES/hOUr 
1OOKB 
TO1[ AL 
ElANDWIDTH 
lOOMEl 
lOMB CHANNEL 
SYSTEM 
 Mb : PACKET 
SYSTEM 
NUMBER OF 
 TERMtNALS 
IOKB __J J [ 1__.,. 
 o oo  OK 00 M 
------------------------------<page break>-----------------------------
--4' 
THE ARPA NETWORK 
A session presented at the Spring Joint Computer Conference, 
Atlantic City, May 16, 1972 and chaired by S, D. Crocker, 
Advanced Research Projects Agency 
 The Terminal IMP For the ARPA Computer 
Network 
 Computer Communication Network Design - 
Experience with Theory and Practice 
 Function-Oriented Protocols for the ARPA 
Computer Network 
 McROSS - A Multi-Computer Programming 
System 
 Extension of Packet Communication Technology 
to a Hand-Held Personal Terminal 
ADVANCED RESEARCH PROJECTS AGENCY 
WASHINGTON, D.C. 
------------------------------<page break>-----------------------------
IN THIS BOOKLET, THE SESSION CHAIRMAN HAS 
APPENDED TO SOME OF THE PAPERS A SUBSET 
OF THE SLIDES PRESENTED AT THE SJCC SESSION. 
------------------------------<page break>-----------------------------
J Mcl Fl LAN '  -)CASE (BBN PROTOTYPE 
,_,...._ _  .,,  w/ 
ARPA NEORK, GEOGRAPHIC MAP; MARCH 19 
------------------------------<page break>-----------------------------
The Terminal IMP for the ARPA computer network* 
by S. M. ORNSTEIN, F. E. HEART, W. R. CROWTHER, H. K. RISING, S. B. RUSSELL 
and A. MICHEL 
Boll Beranek and Newman Inc. 
Cambridge, Massachusetts 
INTRODUCTION 
A little over three years ago the Advanced Research 
Projects Agency of the Department of Defense (ARPA) 
began implementation of an entirely new venture in 
computer .communications: a network that would 
allow for the interconnection, via common-carrier 
circuits, of dissimilar computers at widely separated, 
ARPA-sponsored research centers. This network, which 
has come to be known as the ARPA Network, presently 
includes approximately 20 nodes and is steadily growing. 
Major goals of the network are (1) to permit resource 
sharing, whereby persons and programs at one research 
center may access data and interactively use programs 
that exist and run in other computers of the network, 
(2) to develop highly reliable and economic digital 
communications, and (3) to permit broad access to 
unique and powerful facilities which may be eco- 
nomically feasible only when widely shared. 
The ARPA Network is a new kind of digital com- 
munication system employing wideband leased lines 
and message switching, wherein a path is not es- 
tablished in advance and instead each message carries 
an address. Messages normally traverse several nodes 
in going from source to destination, and the network is 
a store-and-forward system wherein, at each node, 
copy of the message is stored until it is safely received 
at the following node. At each node a small processor 
(an Interface Message Processor, or IMP) acts as 
nodal switching unit and also interconnects the re- 
search computer centers, or Hosts, with the high band- 
width leased lines. 
A set of papers presented at the 1970 S$CC 
described early work on the ARPA Network in some 
detail, and acquaintance with this background ma- 
tehal (especially Reference 2) is important in under- 
' This work w sponsored by the Advanced Research Projects 
Ageaey under Costract No. DAHC15-69~C-0179. 
243 
standing the cur. r.e_; _;ork. The present paper first 
discusses major developments that have taken place 
in the network over the last two years. Wc then de- 
scribe the Terminal IMP, or TIP, a devclopmcnt 
which permits direct terminal access to the network. 
Finally we mention some general issues and discuss 
plans for the next stages in development of the network. 
THE DEVELOPING NETWORK 
The initial installation of the ARPA Network, in 
1969, consisted of four nodes in the western part of 
the United States. A geographic map of the present 
ARPA Network is shown in Figure 1. Clearly, the 
most obvious development has been a substantial 
growth, which has transformed the initial limited experi- 
ment into a national assemblage of computer resources 
and user communities. The network has engendered 
considerable enthusiasm on the part of the participants, 
and it is increasingly apparent that the network repre- 
sents a major new direction in both computer and 
communications technology. 
Figure 2 is a logical map of the network, where the 
Host computer facilities are shown in ovals, all circuits 
are 50 kilobits, and dotted circuits/nodes represent 
planned installations. On this figure certain nodes are 
listed as a "316 IMP"; this machine is logically nearly 
identical to the original IMP, but can handle ap- 
proximately two-thirds of the communication traffic 
bandwidth at a cost savings of approximately one-haLf. 
The orig/nal IMP includes a Honeywell 516 computer, 
and more recently Honeywell began to market the 316 
computer as a cheaper, downward-compatible machine. 
As the network has grown, sites were identified which 
did not require the full bandwidth of the original IMP, 
and a decision was made to provide an IMP version 
built around the 316 computer. Also shown in Figure 2 
are certain nodes listed as "TIP"; th/s new machine 
------------------------------<page break>-----------------------------
244 Spring Joint Computer Conference, 1972 
Figure 1--ARPA Network, geographic map, December 1971 
is discussed in detail later in this paper. Site abbrevia- 
tions shown on Figures 1 and 2 are explained in Table I. 
As the network has grown, a great deal of work has 
been concentrated on the development of Host-to- 
Host protocol procedures. In order for programs 
within one Host computer system to communicate 
with progr,ms in other Hosts, agreed-upon procedures 
and formas must be established throughout the net- 
work. This problem has, as predicted, turned out to be 
a difficult one. Nonetheless protocol procedures have 
evolved and are being accepted and implemented 
throughout the net. At the present writing, many of 
the Hosts have working "network control programs" 
which implement this protocol. Protocol development 
is more fully reported in a companion paper,  but we 
wish to make a general observation on this subject: 
the growth of the network has dynamically catalyzed 
an area of computer science which has to do with the 
quite general problem of how programs should inter- 
communicate, whether in a single computer or between 
computers. Thus the evolution of the Host-to-Host 
protocol represents a side benefit of the network that 
reaches well beyond its utility to the network alone. 
Since both hardware and software network con- 
nections must be implemented by each Host, it is 
important that the external characteristics of the 
IMP be relatively stable. This stability has been care- 
fully maintained, while at the same time internal 
operation of the IMP program has undergone extensive 
.revision and .improvement. For _ex_mp]e, trouble 
reporting, statistics gathering, and"'est-procedures 
have been substantially improved. In addition to im- 
provements that have already been incorporated into 
the program, there have also been extensive studies of 
performance and message flow control. 7 These studies 
have pointed up areas of vulnerability to perverse 
TABLE I--Site Abbreviations 
NCAR 
GWC 
SRI 
MCCLELLAN 
UTAH 
ILLINOIS 
MIT 
LINCOLN 
RADC 
CASE 
AMES 
USC 
UCSB 
STANFORD 
SDC 
BBN 
CARNEGIE 
MITRE 
ETAC 
UCLA 
RAND 
TINKElt 
HARVARD 
BURROUGHS 
NBS 
National Center for Atmospheric Research. 
Global Weather Central 
Stanford Research Institute 
McClellan Air Force Be 
University of Utah 
University of Illinois 
Massachusetts Institute of Technology 
M.I.T. Lincoln Laboratory 
Rome Air Development Center 
Csc Western Reserve 
N.A.S.A. Ames Research Center 
University of Southern California 
University of California at Santa Barbara 
Stanford University 
Systems Development Corporation 
Bol Beranek and Newman 
Carnegie University 
MITRE Corporation 
Environmental Technical Applications 
Center 
Universits' of California at Los Angeles 
ILand Corporation 
Tinker Air Force Bse 
Harvard University 
Burroughs Corporation 
National Bureau of Standards 
heavy traffic patterns and have suggested still other 
possible improvements in the routing and flow control 
mechanisms. Potential changes are presently being 
being studied in some detail and will be incorporated 
into one or more forthcoming major }eVisions of the 
program. They will hopefully anticipate problems 
which might be expected to arise as traffic flow in the 
network becomes heavier. 
Somewhat belatcdly in the network design, the need 
to connect a single IMP to several Hosts was recog- 
nized. This required multiple Host interfaces at the 
.iMP as well as more complex IMP software. Fuher, 
the various Host computers at a site are often physically 
Figurc 2--AI{.PA Network, logical map, December 1971 
------------------------------<page break>-----------------------------
The Terminal IMP 245 
distant from one another, thus requiring an increase in 
the maximum allowable physical separation between a 
Host and its IMP. To connect to an arbitrarily remote 
Host would have meant a communications interface 
capable of attachment to common-carrier circuits via 
modems. It would furthermore have required coopera- 
tive error control from the Host end. At the time, we 
chose not to modify the logical way in which the IMP 
dealt with the Host and instead we provided more 
sophisticated line drivers which would handle distances 
of up to two thousand feet. Several such "Distant Host" 
installations are now working in the network. Un- 
fortunately, as the network has growre, new sites have 
appeared where still greater Host/IMP distances are 
involved. The present scheme does not include error 
control, and use of this scheme over greater distances 
is not appropriate. At the present time we are therefore 
considering how best to arrange IMP/Host connec- 
tions over large distances and additional options will 
be required in this domain. 
Another facility which has been tested is the ability 
of the IMPs to communicate over 230.4 kilobit phone 
lines instei of 50 kilobit lines. A short, fast link was 
incorporated into the network for a brief period and 
no problems were encountered. To date, network 
loading has not justified upgrading any operational 
network circuits to 230.4 kilobits, but this will be con- 
sidered as loading rises. 
Substantial effort has gone into traffic and trouble 
reporting. A Network Control Center (NCC) has been 
built at Bolt Beranek and Newman Inc. in Cambridge, 
where a small dedicated Host computer receives re 
ports each minute from every IMP on the network. 
Traffic summaries and status and trouble reports are 
Figure 3--TypicM segment of NCC log 
then generated from this material. Specifically, a 
logger records any changes that the IMPs report to the 
NCC; it records line errors and IMP storage counts 
when they exceed certain limits, as well as unusual 
events, such as reloading from the net, checksum errors, 
etc. Figure 3 shows an example of this log. (The com- 
ments, in parentheses to the right, are not part of the 
log but have been added to eXl_.Sin the meaning of the 
entries.) In addition to this detailed log of interesting 
events, one may at any time obtain a quick summary 
of the status of the network. Finally, detailed and 
summary logs of Host and line traffic are produced. 
The NCC is a focal point not only for monitoring the 
network but also for testing and diagnosing remote 
troubles. Lines throughout the network can be looped 
from here in order to isolate difficulties. Personnel of 
the center coordinate all debugging, maintenance, 
repair and modification of equipment. 
DIRECT TERM I NAL ACCESS 
During the early phases of network development 
a typical node has consisted of one or more large time- 
shared computer systems connected to an IMP. The 
IMPs at the various sites are connected together into 
a subnet by 50 kilobit phone lines and the large Host 
computers communicate with one another through 
this subnet. This arrangement provides a means for 
sharing resources between such interconnected centers, 
each site potentially acting both as a user and as a 
provider of resources. This total complex of facililies 
constitutes a nationwide resource which could be made 
available lo users who have no special facililies of lheir 
own lo conlribue to lhe resource pool. Such a user might 
be at a site either with no Host computer or where the 
existing computer might not be a terminal-oriented 
time-sharing system. 
A great deal of thought went into considering how 
best to provide for direct terminal access to the net- 
work. One possibility, which would have essentially 
been a non-solution, was to require a user o dial direct 
to the appropriate Host. Once connected he could, of 
course, take advantage of the fact that that Host was 
tied to other Hosts in the net; however, the network 
lines would not have been used to facilitate his initial 
connection, and such an arran'enent limits the ter- 
minal bandwidth to what may be available on the 
switched common-carrier networks. 
A similar solution was to allow terminals to access 
the network through a Host at a nearby node. In such 
a case, for example, a worker in the New England area 
wishing to use facilities at a California site might 
connect into a loca! Boston Host and use that Host 
------------------------------<page break>-----------------------------
246 Spring Joint Computer Conference, 1972 
a.s a tap into the network to get at the facilities in 
California. This approach would havc required Hosts 
to provide hardware access facilities for many ter- 
minals which would us(. their systems only in passing. 
For many Hosts, the. kinds of terminals which can be 
connected directly are limited in speed, character set, 
etc. In terms of reliability, the user would have been 
dependent on the local Host for access: when that Host 
was down, his port into the network would be un- 
available. Furthermore, the Hosts would have been 
confronted with all of the problems of composing 
terminal characters into network messages and vice 
versa ms well as directing these messages to the proper 
terminals and remote Hosts. Time-sharing systems are 
generally already overburdened with processing of 
characters to and from terminals and many are con- 
figured with front end processors employed explicitly 
to off-load this burden from the main processor. In- 
creasing the amount of such work for the Hosts there- 
fore seemed unreasonable and would have resulted in 
limiting terminal access. Instead, a completely separate 
means for accessing the network directly seemed called 
for: an IMP with a flexible terminal handling capa- 
bility--a Terminal IMP, or TIP. 
One of the fundamental questions that arises when 
considering this problem is: what is the proper dis- 
tribution of computational power among the remote 
big facility, the terminal processor, and the terthinal? 
Shall the terminal processor be clever, have sizable 
storage, be user programmable, etc., or shall it be 
simpler device whose basic job is multiplexing in a 
flexible way? Serious work with interactive graphics 
seems to require the terminal to include, or be in 
propinquity to, a user-programmable processor and 
considerable storage. To date, such work has primarily 
been done with terminals attached directly to a Host. 
Some elaborate terminals, such as the Adage, include 
a powerful processor. Other kinds of terminals, in, eluding Teletype-like devices, alphanumeric displays, 
or simple graphic displays (excluding serious inter- 
active graphics), do not require a user-programmable 
local processor or significant local storage. 
Wc believe that the great majority of potential 
groups needing access to the ARPA Network will not 
need powcrful interactive graphics facilities. Further, 
for the minority that will need powerful terminals, wc 
believe that individual terminals with builtAn or 
accompanSng proc.essors will become more common. 
For these reasons, we decided that the terminal pro- 
cessor should be simple and not programmable from 
the terminals. The computational load and the storoqc 
should bc in the Hoss or in the tcrmiTm.s and not in the 
terminal processor. This simple multiplexing approach 
is amenable to some standardization and is 
sophieally close to the original IMP notion of a stan- 
dard nodal device. 
Another major question wc faced was whether to 
build a separate terminal handler and then connect it 
to the IMP or to build an integrated unit that was 
housed in a common cabinet and ud the IMP pro- 
cossot. One advantage of .the two, mi_ne - approach 
is that it isolates the IMP functions from the terminal 
functions, thereby providing a barrier of safety for the 
net. This approach also provides the processing power 
of two machines and a potentially greater degree of 
user freedom in modify/ha or writing program.s. 
Another interesting reason for considering separate 
machines was to reduce the large cost assoclated with 
I/0 equipment (such as line controllers) by making 
use of the extra processing power. We discussed with 
several manufacturers the possibility of bringing 
terminal wires "into" their processors and decoding 
the basic line information directly in software. How- 
ever, even with some of the new state-f-the-art 
machines, like the Meta4, with fast 90 nsec read-only 
memories to handle character decoding, the I/0 cost 
was still high, and in large part the necessary 
equipment was yet to be designed. We therefore con- 
cluded that it was still somewhat early to proceed in 
this fashion, and two processors did not appear to save 
I/0 equipment. 
The principal disadvantages of the two-machine 
approach were the higher initial cost, the difficulties 
of maintaining two machines, and the software problems 
of dealing with two machines. In particular, the com- 
munication between two machines would require two 
hardware Host interfaces, and two software Host/IMP 
programs. This would result in a much poorer com- 
munication between the IMP program and the ter- 
minal handling program than would exist in a single 
machine. In either case, one machine or two, the 
Fgure 4--A TIP in the network 
------------------------------<page break>-----------------------------
The Terminal IMP 247 
terminal handling process required the implementa- 
tion of a version of Host protocol. 
Wc finally decided that the least, expensive and most 
sensible technical alternative was to build the IMP 
and the terminal handler (with the necessary subset 
of Host protocol) together into a single machine. Then, 
since certain new machined-pcxed attractive in 
cost/performance relative to the Honeywell 16 series, 
we spent considerable time thinking about what 
machine to use. We decided that no alternate choice 
was sufficiently attractive to justify rewriting the 
main IMP program and redesigning the Host and 
modem interface hardware. This left us with a de- 
cision between the Honeywell 516 and 316 computers. 
We chose the 31(3 on the basis of size and cost, feeling 
that the somewhat higher bandwidth of the 51'6 was 
not essential to the job and did not justify its higher 
price and the second cabinet which would have been 
required. 
TERMINAL IMP HARDWARE 
Figure 4 shows how the TIP fits the user into the 
network. Up to 63* terminals, either remote or local, 
of w/dely diverse characteristics may be connected to 
a given TIP and thereby "talk" into the network. It is 
also possible to connect a Host to a TIP in the usual 
way. 
The TIP is shown in Figure 5. It i} built around a 
Honeywell /t-316 computer with 201( (20,480 words) 
of core. It embodies a standard 16 port multiplexed 
memory channel with priority interrupts and includes 
a Teletype for debugng and program reloading. 
Other features of the standard IMP also present are 
a real-time clock, power-fail and auto-restart mecha- 
nisms, and a program-generated interrupt feature? 
As in the standard IMP, interfaces are provided for 
connecting to high-speed (50 kilobit, 230.4 kilobit, 
etc.) modems as well as to Hosts. The single-cabinet 
version limits tile configuration to a total of three 
modem and/or Host interfaces, bu an expansion 
cabinet may be used to increase this limit. Riore basic 
limits are set by the machine's logical organization 
(specifically the number of available memory chan- 
nels) and the program bandwidth-capability as dis- 
cussed below. 
Aside from the additional 8K of core memory, the 
primary hardware feature which distinguishes the 
TIP from a standard 1MP is a Multi-Line Controller 
(MLC) which allows for connection of crminals to tile 
' Tilere are 134 hardware lines but lJIc 0 is logicall)' reserved by 
Figure 5Photograph of TIP the program for special 
------------------------------<page break>-----------------------------
248 Spring Joint Computer Conference, 1972 
IMP. Any of the MLC lines may go to loch] terminals 
or via modems l.o re]note termixmls. As shown in 
],'igure 6 the MLC consists of two pro%ions, one a 
of central logic which handles lhc assembly and disas- 
sembly of characters and ransfers them to and from 
memory, and the other a set of individual Line Inter- 
face Uni (all identical except for small number of 
option jumpers) which synchronize reporting to in- 
dividual data bits between the central logic and the 
terminal devices and provide for control and status 
information to and from the modem or device. 1,inc 
Interface Uni may be physically incorporated one at 
a time  required. 
The MLC connects to the high-speed multiplexed 
memory channel option of the H-316, and uses three 
of its channels  well as two priority interrupts and a 
small number of conLrol instructions. The MLC 
fabricad by BBN and is built from TTL integrated 
circuit. The MLC central controller, complctc with 
power supply, is housed in an H-316 expansion chassis, 
and he entire MLC,  well as the computer itself, 
is mounted in a standard six-foot rack. Additional 
space is provided in the bottom of the rack for up to 
sixteen card-mounted modems of the Bell 103, 201, or 
202 variety, together with their power stapplies. 
In order to accommodate a variety of devices, the 
controller handles a wide range of data rates and 
character sizes, in both synchronous and asynchronous 
modes. Data characters of lenh 5-, , 7-, or 8-bits 
are allowed by the controller. Since no interpretation 
of characters is done by the hardware, any character 
set, such  Baudot, Transcode ASCII or EBCDIC 
may be used. 
The follodng is a list of data rates accepted by the 
controller: 
SYNCHRONOUS 
Any rate up to and in- 
cluding 19.2 Kb/s 
A SYNCHRONOUS 
(Nominal Rates) 
75 1200 
110 1800 
134.5 2400 
150 4s00! 
300 9500 t output on]5' 
600 19200J 
All above in bits/second 
The data format required of all devices is bit serial 
and each character indicates its own beginning by 
means of a star[ bit which urccedes the data and in- 
cludes one or more stop bios at the end of the char- 
acter. This per-character framing is quite standard 
for asynchronous lines but synchronous lines, generally 
designed for higher bandwidths, freqne:tty adopt 
some form of "binary synchronous communication" 
where the characters arc packml tightly togclhr'r into 
nl('ssagcs w}lic}l ltrc then framed by special characters. 
l"raming is thcr'l)y amorlized m'(.' the mHirc m,ssage, 
lltls-conStllllillg a smaller fx'm'tim of t]lc 11vailll})l, 
bandwidth than the pcr-characr framing whid 
two or more lilts for evex'y character. The difficulties 
with lifts scheme, hrm'cvcx', arc l.h'(:i:'- i core complex, 
requiring more sop}fisticated hardware at each end. 
and t]mt no real standards exist which are adhex'ed 
})y all or even most types of syndn'cmmxs devices. Wc 
therefore decided to) adopt per-,hax'actcr framing with 
start and stop bits even on synHx'onous lines. At 
cost of some twenty percent of the luredwidth for 
framing, a very simple aml general scheme is thus 
arrived at. A number of high speed terminal manu- 
factux'ex-h, faced with the same problems, have arrived 
at a similar conclusion. 
Given these characteristics, then, the controller will 
connect to the great m!jority of normal terminal de- 
vices such as Teletypes, alphanumeric GIfT units, and 
roMeres, and also (with suitable remote interface 
units) to many peripheral devices such as card readers, 
line printers, and graphics terminals. Either full or 
half duplex devices can he accommodated. The stan- 
dard TIP program cannot deal with a magnetic tape 
unit thx'ough the MLC. However, as a special uplion, 
and with the use of additional core memory, standard 
Honeywell rope drives can be connected to the TIP 
as normal peripherals. 
The individual terminal line levels are consistent 
with EIA RS-232C convention. Data rates and char- 
acter length are individuMly set for each line bg 
the program. For incoming asynchronous lines, the 
program includes the capability for detecting char- 
acter length and line data rate as discussed below. 
LogicalIs', the controller consists of 6 input ports 
and 64 output ports. Each input/output pair is brought 
out to a single connector which is normaIts, connected 
to a single device. However, by using a special "Y" 
MULTI-LiNE CONTROLLER 
I 
[ 
L_ 
Fgurc 6--Bl(>ck diagram ( TIP lmrdwarc 
------------------------------<page break>-----------------------------
The Terminal IMP 249 
cable, the ports may go to completely separate devices 
of entirely different properties. Thus, iaput port 16 
may connect to a slow, asynchronous, 5-bit character 
keyboard while output port 16 connects to a high speed, 
synchronous display of some sort. In order to achieve 
this flexibility, the MLC stores information about each 
input and each output port and the program sets up 
this information for each half of each port in turn as 
it turns the ports "ON." 
Several aspects of the MLC design are noteworthy. 
The central logic treats each of the 64 ports in suc- 
cession, each port getting 800 ns of attention per cycle. 
The port then waits the remainder of the cycle (51.2 
s) for its next turn. For both input and output, two 
full characters are buffered in the central logic, the one 
currently being assembled or disassembled and one 
further character to allow for delays in memory ac- 
cessing. 
During input, characters from the various lines 
stresn, into a tumble table in memory on a first come, 
first served basis. Periodically a clock interrupt causes 
the program to switch tables and look for input. 
Output characters are fed to all lines from a single 
output table. Ordering the characters in this table in 
such a way as to keep a set of lines of Sdely diverse 
speeds solidly occupied is a difficult task. To assist the 
program in this, a novel mechanism has been built into 
the MLC hardware whereby each line, as it uses up a 
character from the output table, enters a request con- 
sisting of its line number into a "request" table in 
memory. This table is periodically inspected by the 
program and the requests are used in building the next 
output table with the characters in proper line se- 
quence. 
The design of the terminal interface portion of the 
MLC is modular. Each Line Interface Unit (LIU) 
contains all the logic required for full duplex, bit serial 
communication and consists of a basic bi-directional 
data section and a control and status section. The 
data section contains transmit and receive portions 
each with clock and data lines. For asynchronous 
devices the clock line is ignored and timing is pro- 
vide'l by the MLC itself. (For received asynchronous 
characters, timing is triggered by the leading edge of 
the start bit of each character.) 
The control and status monitor functions are pro- 
vided for modems as required by the R8-232C specifi- 
cation. Four outputs are available for control functions 
and six inputs are available to monitor status. The 
outputs are under program control and are available 
for non-standard functions if the data terminal is not 
a modem. For example, these lines could be used to 
operate a local line printer. ]LS-232G connectors are 
mounted directly on the LIU cards. To allow for varia- 
tions in terminal and modem pin assignments, the 
signals are brought to connector pins via jumpers on 
the card. 
The central MLC contains 256 lCs, many of which 
are MSI and some of which are LSI circuits, and it is 
thus about the same complexity as the basic H-316. 
In addition each LIU contains qt-IC--. A Terminal 
IMP including the MLC and with a typical interface 
configuration to high-speed circuits and Hosts is, ordcr 
of magnitude, a $100,000 device. 
THE TERMINAL USER'S VIEW 
This section describes how a TIP user gains access 
to the network. The protocol described is of very 
recent origin and will undoubtedly change in response 
to usage which, as of this writing, is just commencing. 
In general a user must have some foreknowledge of 
the resource which he expects to access via the network. 
The TIP program implements a set of commands s for 
connecting to and disconnecting from remote sites, 
but once a terminal is connected to a particular system, 
the TIP becomes transparent to the conversation 
unless specially signalled. This is equivalent to a time- 
sharing system where the executive program is es- 
sentially out of the picture during periods while the 
user is dealing directly with his oxm set of programs. 
Because of the large number of different terminal 
types used in the network, the concept of the Network 
Virtual Terminal was developed. This is an imaginary 
but well-defined type of terminal. The TIP translates 
typed data to virtual terminal code before shipping it 
into the network, and conversely translates the remote 
system's response back into the local terminal's code. 
Thus, each Host system must deal only with this 
single terminal type. 
When the user at a terminal needs to talk directly 
to his TIP instead of to the remote Host, he issues a 
command which is distinguished by the fact that it 
always starts with the symbol . One or more words, 
perhaps followed by a single parameter, then identify 
the type of command. 
NormalIs' a user will go through four more or less 
distinct stages in typing into the, net. First, he will 
be concerned with hardware, power, dialing in, etc. 
Then hc will establish a dialogue with the TIP to get 
a comfortable set of parameters for his usage. Ncxl, 
he will instruct the TIP to make a connection to a 
remote Host, and finally, he will mostly ignore the TIP 
as hc talks to the remote Host. 
One of the more intcrcsting features of hc TIP is 
that it permits great tlcxibility in the types of ter- 
minals which may be attached to any por. Tiffs 
------------------------------<page break>-----------------------------
250 Spring Joint Computer Conference, 1972 
TABLE II--Tip Command 
CLOSE 
cloe all outstanding onnections 
HOST  
foetin attention on this hot 0 <# <256 
LOGIN 
start the initial connection procedure to get Telnet 
connections 
SEND BREAK 
send a Telnet break character 
SEND SYNC 
send a Telnet sync character and an INTERRUPT 
SENDER measage 
ECHO ALL 
local TIP-generated echo--TIP echoes everything 
:ECHO NONE 
remote Hos-gcnerated echo--TIP will echo commanda 
:ECHO HALFDUPLEX 
terminal-generated echo--TIP echoes nothing 
FLUSH 
dele all characters in input buffer 
TRANSMIT EVERY  
sen" nff input buffer at least every th character 
TRANSMIT ON EVERY CHARACTER 
like TRANSMIT EVERY 1 
TRANSMIT ON LINEFEED 
send input buffer every time a linefeed encountered 
TRANSMIT ON MESSAGE-END 
send input buffer every time an EOM encountered 
TRANSMIT ON NO CHARACTER 
do not transmit on linefeed or EO, 
TRANSMIT NOW 
send off input buffer now 
DEVICE RATE  
 is  13 bit code specifying hardware rate and ehar&cter 
size settings 
DEVICE CODE ASCII 
DEVICE CODE 2741 ,establish code 
DEVICE CODE EXECUPORT conversion 
DEVICE CODE ODEC 
SEND TO HOST # establish parameters 
RECEIVE FROM HOST I/ for manual initiation of 
SEND TO SOCKET  connections 
RECEIV:E FROM SOCKET # 
PROTOCOL TO TRANSMIT 
PROTOCOL TO RECEIVE [initiate connection 
PR. OTOCOL TO CLOSE TRANSMIT protocol manually 
PROTOCOL TO COSE RECEIVE 
PROTOCOL BOTH abbreviations for 
PROTOCOL TO CLOSE BOTH simultaneous transmit 
and receive protocol 
# GIVE BACK 
release control of captured device 
# DIVERT OUTPLOp 
capture device / and divert this termina}'s output o it 
ABORT LOGIN 
abort the outstanding initial connection procedure 
flexibility presents a problem to the program which 
must determine what kind of terminal (speed, char- 
acter size, etc.) is attached to a given port before a 
sensible exchange of information is possible. To solve 
this problem, each terminal is assigned a special 
identifying character which the .usej-.y_p.es repeatedly 
when starting to use a terminal: 'hen information 
starts to appear from a previously idle port, the TIP 
enters a "hunt" mode in which it interprets the ar- 
riving characters trying various combinations of 
terminal characteristics. All except the proper com- 
bination will cause the character to be garbled, pro- 
ducing something other than one of the legal ,erminal 
identifying characters. When the TIP thus identifies 
the correct set (which generally requires the user to 
repeat the identifier less than half a dozen times), 
it types out 'HELLO in the term]hal's om language. 
In the next stage, the user initializes certain convet- ' 
sation parameters relating to message size and when 
to echo. He then establishes connection to a remote 
site using two commands which identify the desired 
remote site and the fact that the user wishes to be 
connected to the logger at that site. These comnands 
are: 
@ HOST 15 
 LOGIN 
The LOGIN command actually ses in motion an 
elaborate exchange of messages between the TIP and 
the remote Host which normally result in a connection 
being made to that remote system. This command will 
be answered by an appropriate comment to the user 
indicating either that a connection has been made, that 
the remote site is not up, that it is up but actively re- 
fusing to converse, or that it is up but not responding 
enough even to refuse the connection. 
Once a connection is established, the user types 
directly to the logger. The TIP does not execute the 
actual login since this procedure varies from site to 
site. 
Throughout the user-to-Host dialogue, commands 
remain available at any time. Prior to closing the con- 
nection, the user must log out as required by the 
system he is using. He then gives the command 
 CLOSE 
which causes the TIP to close the connection, in- 
forming the user when the process is finished. 
:In addition to the above more or less standard pro- 
cedures, there are a number of less usual commands 
which set such things as device rate, character size, 
code iypcs, etc. Such commands arc used by a terminal 
on one port in setting parameters for a non-interactive 
terminal, such as a pnter or card reader, on some 
------------------------------<page break>-----------------------------
The Terminal IMP 251 
other port. Other special commands permit conversa- 
tions directly between terminals on the same or dif- 
ferent TIPs, allow for binary mode, etc. Table II is 
a list of the commands with a brief explanation. For 
details refer to Reference 8. Figure 7 gives an example 
of typical dialogue. 
THE SOFTWARE 
Because the terminals connected to a TIP com- 
municate Mth Host at remote sites, the TIP, in ad- 
dition to performing the IMP function, also acts as 
intermediary between the terminal and the distant 
Host. This means that network standards for format 
and protocol must be implemented in the TIP. One 
can thus think of the TIP software as containing both 
a very simpleminded mini-Host and a regular IMP 
program. 
Figure 8 gives a simplified diagrammatic view of the 
prcg:am. The lower block marked "IMP" represents 
the usual IMP program. The two lines into and out 
of .iat block are logically equivalent to input and 
output from a Host. The code conversion blocks are 
in fact surprisingly complex and include all of the 
material for dealing with diverse (and perverse) types 
of terminals. 
As the user types on the keyboard, characters go, 
via input code conversion, to the input block. Infor- 
mation for remote sites is formed into regular network 
messages and passes through the OR switch to the 
IMP program for transmittal. Command characters 
are fed off to the side to the command block where 
commands are decoded. The commands are then "per- 
Figure 7--Typical terminal user dialogue 
Figure 8--Block diagram of TIP program 
formed" in that they either set some appropriate param- 
eter or a flag which calls for later action. An example 
of this is the LOGIN command. Such a command in 
fact triggers a complex network protocol procedure, 
the various steps of which are performed by the PRO- 
TOCOL block working in conjunction with the remote 
Host through the IMPs. As part of this process an 
appropriate special message will be sent to the terminal 
via the Special Messages block indicating the status 
(success, failure, etc.) of the procedure. 
Once connection to a remote Host is established, 
regular messages flow directly through the Input block 
and on through the IMP program. Returning responses 
come in through the IMP, into the OUTPUT program 
where they are fed through the OUTPUT Code Con- 
version block to the terminal itself. 
Storage for the TIP program, including the standard 
IMP program, is just over 20K. This is roughly as 
follows: 
Standard IMP Program with buffers 
& tables 12,000 
Special TIP code 2,650 
Tables of Parameters 1,800 
Buffer Storage for messages t and 
from terminals 1,880 
MisccLlaneous--I/O buffers, con- 
stants, etc. 1,880 
PERFORMANCE 
The program can handle approximately 100 kilobits 
of one-way terminal traffic provided the message size 
------------------------------<page break>-----------------------------
252 Spring Joint Computer Conference, 1972 
is suffie. iently large that per-message I)roeessing is 
amortized over rillill}' (:}ulract(:r.s. ()verhea] pe.r mcssge 
is such t}mt if individual c}mractcrs arc sent one at a 
time there is a loss of somewhere between a factor of 
ten and twenty in bandwidth. A different way to look 
at program performance is to o})serve that the per- 
character proceding time is about 75 us. 
These figures ignore the fact that the machine must 
devote some of its bandwidth to acting as an IMP, 
both for terminal trac and for regular network 
traffic. About 5% of the machine is lost to acting as an 
IMP, even in the absence of traffic. If there is network 
traffic, more of the machine bandwidth is used up. 
I,'ive hundred kilobi of twoway phone line and 
Host traffic saturates the machine without any ter- 
minal traffic*. 
In addition to bandwidth which goes into the IMP 
part of the job, another 10 percent of the (total) ma- 
ckinc is .aken up simply in fielding clock interrupts 
from 'd,c Multi-Line Controller. This again is band- 
width used in idling even with no actual terminal 
traffic. 
The follong formula summarizes, approximately, 
the bandwidth capabilities: 
P + H + 11T  850 
wh ere: 
P  total phone line traffic (in kilobits/see) 
wherein, for example, a full duplex 50 Kb 
phone line counts as 100; 
H = total Host traffic (in kilobits/see) wherein 
the usual full duplex Host interface, with 
its usual 10 us/bit setting, counts as 200; 
and 
T -- total terminal traffic (in kilobits/see) wherein 
an ASCII terminal such as a (110-baud) 
full-duplex Teletype (ASR-33) counts as 
twice its baud rate (i.e., 0.220 Kb). 
This means that it takes eleven times as much 
program time to service crew terminal character as 
it does to service a character's worth of phone line 
or Host message. 
A further factor that influences terminal traffic 
handling capability has to do with the terminals 
themselves. Certain types of terminals require more 
attention from the program than others, indepcndmt 
of their speed but based rather on their comp}exity. 
In particular, for example, while an IBM 2741 nora- 
' The number 500 kilobits is for full size (8000 bit) messages. 
Shother messages use up more cpbility per bit al,d thu reduce 
the overall bandwidth capability. 
insfly runs at 134.5 hits per second, the complexity 
is .such that it uses nearly three times the prngram 
bandwidth that would be used in scrvicin a ball- 
duplex ASCII termthai of equivalent speed. Allow- 
am:es for such variations must bc made in computing 
the macbine's ability to service a paicular conligura- 
tion. It must be borne in mind thxt'::al f these per- 
formsnee figures are approximatirms and that the 
actual rules are extremely complex, and will change 
 the program matures. 
DISCUSSION 
As the ARPA Network grows, a number of areas 
of development seem likely to require attention. Cer- 
tain of these are already pressing problems whereas 
others will begin to appear primarily as the network 
continues to grow and mature. 
Perhaps the most difficult aspect of a network such 
as this is the problem of reliability. A great deal of 
thought and effort has gone into trying to make the 
system reliable and network topology has been de- 
signed with the need for redundancy in mind. None- 
theless the problem of keeping a large number of 
computer systems going at widely separated sites is 
non-trivial. An IMP's mcan-time-between-failure 
(MTBI,') has been on the order of one month; con- 
siderably lower than expected. The problems arise 
from a variety of sources and the system is sufficiently 
complex that frequently the cause has been masked 
by the time the failure has been noted. Often the same 
failure w/11 recur several times until the problem is 
identified and eliminated and this fact tends to decrease 
the apparent MTBF. In general a preponderance of 
the troubles stem from hardware failures, and we are 
currently modifying several noisy and/or marginal 
portions of the I/0 and interface hardware in hopes 
of obtaining significant improvement. 
Our strategy has generally been to spend time 
identifying the source of trouble, keeping the machine 
off the air if necessary, so that eventually the MTBI,' 
will increase. This has often meant, bowever, that 
a "down" was much longer than it would }lave been, 
had the foremost goal been to get the machine running 
again immediately. With this strategy the average 
down time bas been about 9 hours, giving rise to an 
average per-machine down rate of allout 2 perten[. We 
hope to improve this si[uation in the near future by 
providing improved facilities for obtaining "program 
dumps" when a failure occurs. This will make it possible 
to bring machines back on tile air almost immediately 
in many cases, without jeopardizing valuable de- 
bugging data. 
------------------------------<page break>-----------------------------
The Terminal IMP 253 
A word about our experience with the phone lines 
appears appropriate here as well. We have apparently 
been an unusual, if not unique, customer for the com- 
mon carriers in our degree of attention to line failures. 
Our ability to detect and report even brief outages has 
led through measured skepticism to eventual accept- 
ance by the carriers. In general, tests have indicated 
that the phone line error rates are about as predicted, 
i.e., approximately one in 10 . These occasional errors 
or error bursts do not appear to affect network per- 
formance adversely. The IMP-to-IMP error checking 
procedure has not, to our knowledge, admitted a 
single erroneous message. We have, however, had 
some difficulty with lines which were simply out of 
commission from Lime to time for extended periods 
(hours or even days). The reliability of the phone lines 
is roughly equivalent to the reliability of the IMPs, 
based on the number and duration of outages. 
times have decreased as the carriers have come to 
rcf.cpt our complaints as generally legitimate. Overall 
the performance of the telephone equipment does not 
appear to constitute a problem i etwork growth. 
From a strictly technical viewpoint we view the in- 
corporation of higher bandwidth facilities as a natural 
and key part of network growth. Whi}c the present 
facilities arc not saturated by the present loads, we 
view this situation as a temporary one and something 
of a period of grace. As the network continues to grow 
over the next few years traffic can be expected to in- 
crease in a very non-linear fashion. Host protocol 
procedures (which have presented a sizable stumbling 
block to usage) are settling down so that software 
commitments can be made, and the advent of the 
Terminal IMP will bring an influx of new users who 
do not have the alternative of local resources. As a 
result we expect that traffic xxqll beg/n to saturate 
some parts of the network. TerminaI IMPs may well 
be called upon to service a larger number of terminals 
of higher bandMdth than can be handled by the 
present version. 
In anticipation of these requirements we are presently 
considering the design of a significantly faster and 
more modular version of the IMP. Its higher speed 
will permit it to take advantage of high speed (i.e., 
megabit and above) communication lines which the 
common carriers are currently developing. More 
generally it will be able to service high bandwidth 
requirements whenever and however they occur xqthin 
the net. We arc currently studying a modular design 
which will permit connection of a greater number of 
interfaces than the present IMP can handle. While 
this work is only in the preliminary design stage, we 
feel that the interest and enthusiasm which have 
greeted the initial network suggest that it is not too 
early to consider ways 1,o cope x5th grovSng traffic 
requirements. 
Another area of network development which has 
already received a great deal of attention and will 
require much more in the future is that of technical 
information interchange between the sites. To the 
user, the resources which arer. becoming available are 
staggering if not overwhelming. It is very difficult for 
an individual to discover what, if any, of the mass of 
programs that will be available through the network 
may be of interest or of use to him. To aid in this 
process a number of mechanisms are being implemented 
and we are cooperating closely Mth these efforts. In 
particular, at the Stanford Research Institute a Net- 
work Information Center (NIC) acts essentially as 
a library for documental, ion concerning the network. 
Here are maintained a number of pointer documents, 
specifically, (1) a Directory of Participants which lists 
critical personnel, phone numbers, etc., for each par- 
ticipating site, (2)'a catalogue of the NIC Collection 
which lists the available documents indexed in a 
variety of ways, (3) a Prosource Notebook which is a 
compendium that attempts to familiarize the reader 
with available program resources at each of the par- 
ticipating sites. 
Finally, there is the broad and exciting issue of how 
to cope with success. As the ARPA Network grows, 
and as diverse resources and users join the net, it is 
clear that a technology transfer must occur; the net- 
work probably must shift from a government-sup- 
ported research and development activity to an 
ongoing national service of some kind. However, the 
computer-communications environment in the U.S. 
is rather complex, and is populated with many legal, 
economic, and political constraints. Within this en- 
vironment, it is not easy to perform the technology 
transfer, and many groups, including ARPA and BBN, 
have been considering possible alternative plans. We 
are optimistic that a way will be found to provide a 
suitable legal and political base for expansion of the 
present ARPA Network into a widely useful public 
communication system. 
ACKNOW LEDG M ENTS 
In addition to tile authors, a great many people have 
contributed to tile work reported here. Dr. L. G. 
Roberts of the Advanced Research Projects Agency 
has continued to lend crucial suppo and encourage- 
ment to tile projeci. Messrs. Blue, Dolan, and Crocker 
of tile ARPA orifice have been understanding and 
helpful. Suggestions and helpful criticism have come 
from many present and prospective participan in 
the network community. 
------------------------------<page break>-----------------------------
254 Spring Joint Computer Conference, 1972 
At BBN, W. B. Barker is responsible for much of 
the cleverness which appears in the MLC hardware; 
R. E. Kahn has contributed in many areas and has 
been deeply involved in udying traffic flow control; 
A. McKenzie has compiled the Network Resource 
Notebook and been concerned with Host relations and 
many Host protocol issues; M. Thrope has managed 
the Network Control Center and has kept the network 
on the air; J. Levin helped in implementation of the 
TIP software; B. P. Cosell has patiently labored with 
the IMP software, with help from J. McQuillan and 
M. Kraley; and R. Alter has offered much helpful 
advice and criticism. 
REFERENCES 
L G ROBERTS B D WESSLER 
Compat'r network development to achieve retource sharing 
AFIPS Conference Proceeding Spring Joint Computer 
Conicfence 1970 
F E HEART R E KAHN S M ORNSTEIN 
W R CROWTHER D C WALDEN 
The interface mezsaqe processor for the A RPA computer 
ntwork 
AFIPS Conference Proceeding Spring Joint Computer 
Conference 1970 
L KLEINROCK 
Analytic and simulation methods in computer network desion 
AFIPS Conference Proceedings Spring Joint Computer 
Conference 1970 
H FRANK ! T FRISCH W CHOU 
Topolofical considerations in the design of the ARPA 
computer network 
AFIPS Conference Proceedings Spring Joint Computer 
Conference 1970 
5 C S CARR S D CROCKER V G CERF 
Hoit-hozt communication protocol in the ARPA network 
AFIPS Conference Proceedings Spring Joint Computer 
Conference 1970 
6 S CROCKER et al 
Function-orieraed protocols for the A RPA computer network 
AFIPS Conference Proceedings Spring Joint Computer 
Conference 1972 
7 R E KAHN W R CROWTHER-':: - :- 
Flow control in a retource sharing computer network 
Proc Second Symposium on Problems in the Optimization 
of Data Communications Systems October 1971 
8 Uer's uid to the terminal IMP 
Bolt Beranek and Newman Inc Report No 2183 
9 The BBN terminal interface message processor 
BBN Report 2184 
10 L G ROBERTS B D WESSLER 
The ARPA network 
Computer Communication Network Chapter 6 In 
preparation 
ll L G ROBERTS 
A forward look 
Jo'nal of Armed Forcez Communications and Electronic 
Aasoc Vol XXV No 12 August 1971 pp 77-81 
12 The M IT Lincoln Lab terminal support procezsor 
Graphic Semi-Annual Tech Summary Report 
ESD-TR-70-151 p 355 May November 1970 
13 Prooets report I 
University of Michigan MERIT Computer Network Report 
0571PR4 May 1971 
14 A B COCANOWER W FISCHER 
W S GERSTENBERGER B S READ 
The coramunicationa computer operating systern--The initial 
University of Michigan MERIT Computer Network 
Manual t1070-TN-3 October 1970 
15 R E KAHN 
Terminal access to the ARPA corapater network 
Conrant Computer Symposium 3 Computer Network 
Courant Institute New York November 1970---Proceedings 
to be published by Prentice Hall Englewood Cliffs New 
Jersey In preparation 
------------------------------<page break>-----------------------------
QUARTER 
NUMBER OF NODES ON NET  MILESTONES 
1969 
1970 
INITIAL CONTRACT AWARDED 
FIRST PROTOTYPE IMP BUILT 
L/ FIRST PRODUCTION IMP SHIPPED TO UCLA 
FOUR-NODE TEST NETWORK IN PLACE 
1 
2 
4 
FIRST TRANSCONTINENTAL LINK, BBN-UCLA 
SRI-UTAH EXPERIMENT 
ROOM TEST 230.4 KB MODEM 
1971 
316 IMP ON NET 
15 HOST- HOST PROTOCOL 
FIRST TIP TO AMES 
RUNN I NG 
1972 I 
HOST COMPUTER TYPES 'NUMBER 
PDP-1 -2 
PDP-10 -1: 
PDP-11 -3 
H316 .1 
H645 -] 
TSP-1 .1 
TX-2 '1 
B6700 '1 
UNIVAC 418 TF]'-2 
SIGMA 7-1 
360/44 -1 
360/65 -1 
360/67' 3 
360/75, 
360/9] 
------------------------------<page break>-----------------------------
MULTI- LINE CONTROLLER CHARACTERISTICS 
 64 LINES 
 CLOCKED /UNCLOCKED 
 START/STOP FORMAT 
 CHARACTER SIZE (5-8 B;,'S) 
 SPEEDS 
CLOCKED ANY UP 
UNCLOCKED-- ALL 
 FULL OR HALF DUPLEX 
 TERMINALS OF MANY TYPES 
 PER LINE PROGRAM- SETTABLE 
(INCLUDING 
TO 19.2 KB 
STANDARD 
SPEEDS 
CHACTERISTICS 
CROSSPATCHING ) 
MULTI-LINE CONTROLLER 
STATUS 
DATA COMMANDS t INTERRUPTS 
{ COMMON LOGIC ! 
LOW SPEED NAL VOICE GRADE 
MODEM (UP PHONE LINE 
TO 9 6KBPS (DIAL IN) 
UP TO 64 LINE 
INTERFACE UNITS 
I 
I 
I 
I 
UP TO 16 
INTERNAL MODEMS 
103 OR 201 OR 202 
I 
J 
------------------------------<page break>-----------------------------
Computer communication network design-- 
Experience with theory and practice* 
by HOWARD FRANK 
Network Analytis Corporation 
Glen Cove, New York 
and 
LEONARD KLEINROCK 
Univertity of California 
Los Angeles, California 
ROBERT E. KAHN 
Bolt Beranek and ,Vewrtmn Inc. 
Cambridge, Massachusetts 
INTRODUCTION 
The ARPA Network (ARPANET) project brought 
together many individuals with diverse backgrounds, 
philosophies, and technical approaches from the fields 
of computer science, communication theory, operations 
research and others. The project was aimed at providing 
an efficient and reliable computer communications 
system (using message switching techniques) in which 
computer resources such as programs, data, storage, 
special purpose hardware etc., could be shared among 
computers and among many uscrs. as The variety of 
design methods, ranging from theoretical modeling to 
hardware development, were primarily employed 
independently, although cooperative efforts among 
designers occurred on occasion. As of November, 1971, 
the network has been an operational facility for many 
months, with about 20 participating sites, a network 
information ccntcr accessible via the nct, and well ovcr 
a hundred researchers, system programmers, computer 
center directors and other technical and administrative 
personnel involved in its operation. 
In this paper, we review and evaluate the methods 
used in the ARPANET design from the. vantage of 
over two years' experience in the development of the 
network. In zTit. ing this paper, the authors have each 
made equal contributions during a series of intensive 
* This work was supported by the Advanced Research Projects 
Agency of the Department of Defense under Contract No. 
DAItC 15-70-G-0120 at tho Network Analysis Corporation, 
Contract Nos. DAHC 15-69-C-0179 and DAItC-71-C4)088 at 
Bolt Beranek and Newman Inc., and Contract No. DAHC 
15-1t9-C-0285 at the University of California at Los Angeles. 
discussions and debates. Rather than present merely a 
summary of the procedures that were used in the 
network design, we have attempted to evaluate each 
other's methods to determine their advantages and 
drawbacks. Our approaches and philosophies have often 
differed radically and, as a result, this has not been an 
easy or undisturbing process. On the other hand, we 
have found our collaboration to be extremely rewarding 
and, notably, we have arrived at many similar con- 
clusions.about the network's behavior that seem to be 
generally applicable to message switched networks. 
The essence of a network is its design philosophy, its 
performance characteristics, and its cost of implementa- 
tion and operation. Unfortunately, there is no generally 
accepted definition of an "optimal" network or (."enc r 
a "good" network. For example, a network designed to 
transmit large amounts of data only during late evening 
hours might call for structural and performance char- 
acteristics far di fierent from one serv/cing large numbers 
of users who are rapidly exchanging short messages 
during business hours. We expect this topic, and others 
such as the merits of message switching va. circuit 
switching or distributed rs. centraSzed control to be a 
subject of discussion for many years. l.'.2',*a.a'.a? 
A cost analysis performed in 1967-1968 for the ARPA 
Network indicated that the use of message switching 
would lead to more economical communications and 
better overall availability and utilization of resources 
than other methods? .*a In addition to its impact on 
the availability of computer resources, this decision has 
generated widespread interest in store-and-forward 
commuaications. In many instances, the use of store- 
and-forward communication techniques can result in 
255 
------------------------------<page break>-----------------------------
256 Spring Joint Computer Conference, 1972 
km.,d,.r fi.xilfilily, hi14hr'r r-hMfilily, sit4nificanl 
th(' us(, of convelll,ional comn(m eartier .ffr,rngs, An 
obviolis tr('ld towiml incrvtsc(1 conl)utcr and 
municati(m interaction bas bugtin. III ati(liti.n to tim 
ARPANIT, research in svveral ]el)oratories is under 
way, small experimental networks are b,ing built, 
a few examples of other governm('nt ltn([ commercial 
networks are alr(:ady apl)arent. .La..l 
In the AI{PANET, (.ach time-sharing or batch 
processing coml)uh'r , called it Host, is c(mnvclcd 1o 
small computer calh'd lkIl Interface Mcssag, Processor 
(IMP). The IMPs, which are interconnected by leased 
50 kilobit/second circuits, 'handle all n('twork com- 
munication for their Hosts. To send a message 
ano[hcr Host, a Host precedes tin: text O( its message 
with an address and simply deliwrs it o its IMP. 
IMPs then determine the route, provide error control, 
and r9tify the sender of its receipt Tim collection 
Hosts, IMPs, and circuits forms the message switched 
resource haring network. A good description of tbc 
ARPA..i , and some early results on protocol develop- 
ment and modeling are given in Rob,fences 3, 12, 15, 
23 and 38. Some experimental utilization of the 
ARPANET is described in Reference 42. A more recent 
evaluation of such networks and a forward look is 
given in References 35 and 39. 
The development of the Network involved four 
principal activities: 
(1) The design of the IMPs to act as nodal store- 
and-forward switches, 
(2) The topological design to specify the capacity 
and location of each communication circuit 
within the network, 
(3) The design of higher level protocols for the use 
of the network by time-sharing, batch pro- 
cessing and other data proccssing systems, and 
(4) System modeling and measurement of network 
performance. 
Each of the first three activities were essentiallb, per- 
formed independently of each other, whereas the 
modeling effort, partly affected the IMP design effort, 
md closely interacted with tiw topokgica! design 
project. 
The IMPs were designed by Bolt Beranek and 
Newman Inc. (BBN) and were buih to operM. c in- 
dependent of the exact network connectivity; the 
topological structure was specified by Network Analysis 
Corporation (NAG) using models of network per- 
formance developed by NAC ad by the University of 
California ut s Angeles (UCLA). The major efforts 
in the area of system modeling were performed at 
UC1.A. To facilitate (.fivetim. use of tbv re't, higlu'r 
}vw.l (user) l)rohmols are under d(,w.lopmvnl by ;t 
gr}ml) of represvntatiw,s of univ?:rsiti(,k and rusearch 
centers. ]'bis group, known as lbc Network Working 
Gruup, has alr(.ady specifi('d a Host Io Host prolocol 
and a Tvtnm protocol, and is in i}n, proc,ss of corn- 
}timing mh-r fimcli(m orienh'd prolocols. .u W, 
no attumpt t vlalmral' on the Host to }lost. protocol 
design probh,ms in Ibis pap('r. 
THE NETWORK DESIGN PROBLE.M 
A variety of performance' requirements and system 
constraints were considered in the design of lhv net. 
Unfortunateb', many of the key design objectives bad 
to be specified long before the actual user r,quiremvnls 
could be known. One('. the decision to ,mploy roessag? 
switching was made, and rift}' kilobit/second circuits 
were chosen, the critical design variables were the 
network operating procedure and the network topology; 
the desired v:ducs of tbroughl)Ul, dr,lay, reli:dfility and 
cost were system performance and constraint variables. 
Other constraints affected the structure of the network, 
but not its overall properties, such as those arising from 
decisions about the length of time a message could 
remain within the network, the location of IMPs 
relative to location of Hosts, and the number of Hosts to 
be handled by a single IMP. 
In this section, we identify the central issues related 
to IMP design, topological design, and network 
modeling. In the remainder of the paper, we describe 
the major design techniques which have evolved. 
IMP properties 
The key issue in the design of the IMPs was the 
definition of a relationship between the IMP subnet 
and the Hosts to partition responsibilities so that 
reliable arid ePficient operation would be achieved. The 
decision was made to build an adt. onomous subnet, 
indq)endent (as much as possible) of tttc operation of 
any Host. The subnet was designed to function as it 
"comnmnications system"; issues concerning fix. use of 
the subnet by the Hosts (such as protocol development) 
were initially left to the Hosts. For rcliabilily, the 
IMPs wcrv designed to b(: robust against all lira: failures 
and the vast majority of IMP and Host failures. This 
dt'cision required routing strategics that dynamically 
adap! to changes in the states of IMPs and circuits, 
------------------------------<page break>-----------------------------
Computer Communication Network Design 257 
and an ebbborate flow control strategy to protect the 
subnet agMrmt Host malfunction and congestion due to 
IMP buffer limittio. In addition,  statisiics and 
status reporting mecimnism was needed to monitor the 
behavior of the network. 
The number of circuits thai an IMP must handle is  
design constraint directly affecting both the structure 
of the IMP and the topological design. The speed of the 
IMP and the required storage for pro,am and buffers 
depend directly upon the total required proceding 
capacity, wch must be high enough to switch traffic 
from one linc to another when all are fully occup]('d. Of 
eat importance is the property that, M1 IMPs operate 
with identicM pro.ams. This technique catly 
simplifies the problem of network planning and main- 
tenante and makes nctwork modifications easy io 
perform. 
The detailed physicM structure of the IMP is not 
diqcuscd in this paper. TM However, the operating 
procedure, which ides packets through the net, is 
very much of interest here. The flow control, routing, 
and error control techniques are inteal parts of the 
operating procedure and can be studied apart from the 
hardware by which they are implemented. Most 
hardware modificatiom require changes to many 
IMPs Mready installed in the field, while a change in 
the operating procedure can often be made more 
conveniently by a change to the single operating 
pro.am common to MI IMPs, which can then be 
propagated from a single location via the net. 
Topological properties 
The topological design resulted in the specification of 
the location and capacity of all circuits in the network. 
Projected Host--Host traffic estimates were known at 
the start to be either unreliable or wrong. Therefore, 
the network was designed under the assumption of 
equal traffic between all pairs of nodes. (Additional 
superimposed traffic was sometimes included for those 
nodes with expectation of higher traffic requirements.) 
The topological structure was determined Mth the aid 
of specially developed heuristic programs to achieve a 
low cost, reliable network with a high throughput and 
a general insensitivity to the exact traffic distribution. 
Currently, only 50 kilobit/second circuits are being 
used in the ARPANET. This speed line was chosm to 
Mlow rapid transmission of short. messages for inter- 
active processing (e.g., less than 0.2 seconds average 
packet delay) as well as to achieve high throughput 
(e.g., at least 50 kilobits/second) for transmission of 
long messages. For reliability, the network was con- 
strained to have a[ least two independent paths between 
each pair of IMPs. 
The topological design problem requires consideration 
of the following two questions: 
(1) Starting with a given state of the network 
topology, what circuit modifications are required 
to add or delete a set of IMPs? 
(2) Starting wi'th a given state of'network topology, 
when and where should circuits be added or 
deleted to account for long term changes in 
network traffic? 
If the locations o[ all network nodes arc known in 
advance, it is clearly most efficient to design the 
topological structure as a single global cffort. Howcvcr, 
in the AR. PANET, as in most actual networks, the 
initia} designation of node locatims is modified on 
numerous occasions. On each such occasion, the 
topology can bc completely rcoptimizcd to determine a 
ncw set of circuit locations. 
In practice, there is a long lead time between thc 
ordering and the delivery of a circuit, and major topo- 
logical modifications cannot be made without sub- 
stantial difficulty. It is therefore prudent to add or 
dcletc nodes with as little disturbance as possible to 
the basic network structure consistcnt with overall 
cconomical operation. Figure 1 shows the evolution of 
the ARPANET from the basic four IMP design in 199 
to the presently planned 27 IMP version. Inspection of 
the 24 and 27 IMP network designs reveals a few 
substantial changcs in topology that takc advantage of 
the new nodes being added. Surprisingly enough, a 
complete "reoptimization" of the 27 IMP topology 
yields a network only slightly less expensive (about 
1 perccnt) than thc present network design? s 
Network models 
The development of an accurate mathematical model 
for the evaluation of time delay in computer networks is 
among the more difficult of the topics discussed in this 
paper. On the one hand, the model must properly 
reflect lhe relevant features of the network structure 
and operation, including practical constraints. On the 
other hand, the model must result in a mathematical 
formulation which is tractable and from which mean- 
ing[ul results can be extracted. However, the two 
requirements are often incompatible and we search for 
an acceptable compromise between these two extremes. 
The major modeling effort thus far has been the study 
of the behavior of networks of qumlcs? This emphasis 
is logical since in roessag(, switched systcms messages 
experience queucing delays as the)' pass from nod(' to 
node and thus a significant performance measure is the 
------------------------------<page break>-----------------------------
258 Spring Joint Computer Conference, 1972 
UCLA UCLA RAND BBN 
NETWORK - 12 / I/69 
LINC SRI UTAH 
SDC 
 
HARV UCLA RAND 
10-NODE NETWORK - 7/1/70 
ILL MIT 
 
CARN 
)BN HARV BURROUGHS 
15-IMP NETWORK- 3/I/71 
(c) 
McCLELLAN 
SAH BOULDER GWC 
$DC hilt ETAC 
ST 
.LA RAND TINKER BBN HARV NBS 
24-IMP NETWORK - 4/1/72 
(d) 
$RI LRL UTAH ILL 
LINC 
UCSB 
RADC 
UCLA $DC USC BOULDER GWC CASE 
27-1MP NETWORK- PLANNED 
Figure 1--The evolution of the ARPANET 
speed at which messages can be delivered. The queueing 
models were developed at a time when there wcrc no 
operational networks available for experimentation and 
model validation, and simulation was the only tool 
capable of testing their validit),. The models, which at 
all times were recognized to be idealized statements 
about. the real network, wcrc nonetheless crucial to the 
ARPANET topological design effort since the), afforded 
the only known way to quantitatively predict the 
properties of different routing schemes and topological 
structures. The models have been subsequently demon- 
strated to be very accurate predictors of network 
throughput and indispensable in providing analytical 
insight into the nctwork's behavior. 
The key to the successful development of tractable 
models has been to factor the problem into a set of 
simpler queueing problems. T]mrc arc also heuristic 
design procedures that one can use in this case. These 
procedures seem to work quite well and arc described 
later in the paper. However, if one specializes the 
problem and removes some of the real constrMnts, 
theory and anaJysis become useful to provide under- 
standing, intuition and design guidelines for the original 
constrained problem. This approach uncovers global 
properties of network behavior, which provide k%,s to 
good heuristic design procedures and ideal performance 
bounds. 
DESIGN TECHNIQUES 
In this section we describe the approaches taken to 
the design problems introduced in the previous section. 
We first summarize the important properties of the 
ARPANET design: 
(1) A communications cost of less than 30 cents per 
thousand packets (approximately a megabit). 
(2) Average packet delays under 0.2 seconds through 
the net. 
(3) Capacity for expansion to 64 IMPs without 
major hardware or software redesign. 
(4) Average total throughput capabilfiy of 10-15 
kilobits/seeoud for all Hosts at an IMP. 
(5) Peak throughput capability of 85 kilobits/second 
per pair of IMPs in an otherwise unloaded 
network. 
(6) Transparent, communications with maximum 
message size of approximat('.ly 8000 bits and 
error rates of one bit in 10 = or less. 
------------------------------<page break>-----------------------------
Computer Communication Network Design 259 
(7) Approximately 98 percent availability o any 
IMP and close to 100 percent availability of all 
operating IMPs from an)' operable IMP. 
The. relationships between the various design efforts 
arc illustrated by these properties. The topological 
design provides for both a desired average throughput 
and for two or more paths to bc full)' used for com- 
munication between any pair of Hosts. The operating 
procedure should allow any pair of Hosts to achieve 
those objectives. The availability of IMPs to com- 
municate reflects both the fact that IMPs arc down 
about 2 percent of the time and that the topology is 
selected so that circuit failures contribute little addi- 
tional to the total system downtime. 
IMP design 
25c IMP design consists of two closely coupled but 
nonetheless separable pieces--the physical hardware 
specification (based on timing and re)ability considera- 
tions and the operating procedure) and the design and 
implementation of the operating procedure using the 
specified IMP hardware. The IMP originally developed 
for the ARPANET contains a 16-bit one microsecond 
computer that can handle a total of about a megabits/ 
second of "useful" information on a total of approxi- 
mately one megabit/second of circuit capacity (e.g., 
twenty 50 kilobit/second circuits). Hardware is likely 
to change as a function of the required IMP capacity 
but an operating procedure that operates well at one 
IMP capacity is likely to be transferable to machines 
that provide different capacity. However, as a network 
grows in size and utilization, a more comprehensive 
operating procedure that takes account of known 
structural properties, such as a hierarchical topology, 
is appropriate. 
Four primary areas of IMP design, namely message 
handling and buffering, error control, flow control, and 
routing are discussed in this section. The IMP prowides 
buffering to handle messages for its Host and packets 
for other IMPs. Error control is required to provide 
reliable communication of Host messages in the 
presence of noisy communication circuits. The design 
of the operating proccdure should allow high through- 
put in the net under heavy traffic loads. Two potential 
obstacles to achieving this objective are: (1) The net 
can become congested and cause the throughput to 
decrease with incrcasing load, and (2) The routing 
procedure may bc unable to ,lways adapt sufficiently 
fast to the rapid movement of packets to insure efficient 
routing. A flow control and routing procedure is 
needed that can efficiently mcct this requirement. 
Message handling and buffering 
In the ARPANET, the maximum message slzc was 
constrained to be approximately 8000 bits. A pair of 
Hosts will typically communicate over the not via a 
sequence of transmitted messages. To obtain delays of 
a few tenths of a second for sucl[tnessgcs and to lowvr 
the required IMP buffer storage, the IMP program 
partitions each message into one or more packets each 
containing at most approximately 1000 bits. Each 
packet of a message is trammitted independently to 
the destination where the message is reassemb}ed by 
the IMP before shipment to that destination Host. 
Alternately, the Hosts could assume the responsibility 
for reassembling messages. For an asynchronous IMP- 
Host channcl, this marginally simplifies the IMP's 
task. However, if every IMP-Host charmel were syn- 
chronous, and the Host provided the reassembly, the 
IMP task can bc further simplified. In this latter case, 
"IMP-like" software would have to be provided in 
each Host. 
The method of handling buffers should be simple to 
allow for fast processing and a small amount of program. 
The number of buffers should bc sufficient to store 
enough packets for the circuits to bc used to capacity; 
thc size of the buffers may bc intuitively selected with 
the aid of simple analytical techniques. For example, 
fixed buffer sizes are useful in the IMP for simplicity 
of design and speed of operation, but inefficient utihza~ 
tion can arise because of variable length packets. If 
each buffer contains A words of overhead and provides 
space for M words of text, and if messsac sizes are 
uniformly distributed between 1 and L, it can bc 
shown  that the choice of M that minimizes the cx- 
pccted storage is approximately -v/X-. In practice, M 
is chosen to be somewhat smaller on the assumption 
that most traffic will bc short and that the amount of 
overhead can be as much as, say, 25 percent of buffer 
storage. 
Error control 
The IMPs must assume the responsibility for pro- 
widing error control. There are-foqar possibilities to 
consider: 
(1) Messages are delivered to their destination out 
of order. 
(2) Duplicate messages are delivered to the 
destination. 
(3) Messages are delivered witL errors. 
(4) Messages are not delivered. 
------------------------------<page break>-----------------------------
260 Spring Joint Computci' Conference, 1972 
The task of proper sequ('ncing of m.ssages for 
delivery to the destination }test sexually falls in llw 
province of both error control and flow control. I[ at 
most. one message at a time is Mlowed in the n't betwm.n 
u pair of Hosts, proper seqtwncing occurs naturally. A 
duplicate packo[ will arriw' at the destination IMP 
after an acknowledent has b,,en miss'd, thus causing 
a successfully received packet to be retrasmitted. The 
IMPs can handle the first two eonditims by assigning 
a sequence number to each pack('t as it enters the 
network and processing the s('quenee number at th,: 
destination IMP. A Host that performs reassembly can 
also sign and process sequence numbers and check 
for duplicate packets. For many applications, the order 
of delivery to the destination is immaterial. For priority 
messages, however, it is typically the ee that fast 
delivery requires a perturbation to the sequence. 
Errors are primarily caused by noise on the com- 
munication circuits and are handled most simply by 
error detection and retrammission between each pair of 
IMPs along the trammission path. This technique 
requires extra storage in the IMP if either circuit 
peeds or eireui[ lenhs substantially increase. FMlures 
in detecting errors can be made to occur on the order of 
years to centuries apart with little extra overhead 
(20-30 parity bits per packet with the 50 kilobit/second 
circuits in the ARPANET). Standard cyclic eor 
detection codes have been usefully applied here. 
A reliable system design imures that each trento- 
mitred message is accurately delvered to its intended 
destination. The occasional time when an IMP fails and 
destroys a useful in-transit message is likely to occur 
far less often than a similar failure in the Hosts and has 
proven to be unimportant in practice, as are errors due 
to IMP memory failures. A simple end to end retrans- 
mission strategy will protect agaimt these situatioxs, 
if the practical need should arise. However, the IMPs 
are designed so that. they can be removed from the 
network without destroying their internally stored 
packets. 
Flow control 
A network in which packets may freely e. nter and 
leave can become congested or logically deadlocked and 
cause the movement of traffic to halt. .* Flow control 
techniques are required to prevent these eonditimm 
from occurring. The provision of extra buffer storage 
x511 mitigate agaist congestion and deadlocks, but 
cannot in general prevent them. 
The sustaimd failure of a destination Host to acc'pt 
packets from its IMP at the rate of arrival will cause 
net to fill up and byteroe cong:sted. Two kinds of 
fogScsi d':alloeks, knmvn :is r,:tssr.mbly l,ekup and 
store-and-forward leekup may also occur. In rcasscmbly 
lockup, l}w r,'maining imct.'Is of Iarlinlly r,'asscmbh,d 
m.ssag.s at{' blrmk.d from r'acbing l}w 
IMP (thus Ire'ringling l}w m.ssag. from 
pitted slid t]W rcassembly spac' fre'd) by other 
packets in tlw m'l that ar. waiting hm r,,ass,m},ly 
at thai d'stination to }weerim fr,e. Ina slorc-and- 
forward lockup, the d,stination hlts room 
arriving Imckcts, bul t}w packels inl'rh.r, with 'ach 
other by tying up buffers in transit in such a way that 
Ilone of the packets ar, a})]' to r'ach tlw d,stinalion. * 
These phenomena haw. only }wen made' to occur during 
w'ry carefully arrang.d testing of the ARPAXET and 
by simulation? 
In the original ARPANET d'sign, the us, of soft- 
ware links and RFN.MS prmected against congestion 
by a singh' link or a small s:t of links. Howew.r, the 
combin'd traffic on a large mm}wr of [inks could still 
produce cong,stion. Although this strategy did not 
protect agaist lockup, the. method has provided ampl'. 
protection for tim levels of trM[e encountered by tim 
net to date. 
A particularly simple flow corntel algrkhm that 
augments the origi hal 1M P design to prewmt congt,sl ion 
and lockup is also d,scribl,d in Rr,fercnce 17. This 
scheme includes a mechanism whereby pack.ts may be 
discarded from the m,t at the destination IMP whm 
congestion is about to occur, with a copy of .aeh dis- 
carded packet to be retrasmitted a short time later hy 
the originating Host's IMP. Rather than experts'nee 
excessive delays within the m't as trac h'w,ts arc. 
increased, the traffic is queued outside the' net so that 
the /rait time delays internal to the net continue to 
remain small. This strategy prew,nts the imertion of 
more traffic into the net than it can handle. 
It is important to note the dual requircm'nt for small 
delays for intractiw' Iraffic and high bandwidth for the 
fast transfer' of files. To allow' high bandwidth between 
a pair of Hosts, the ncl must b, able to accept a steady 
flow of packets from one Host and at the same time be 
able to rapidly quench the flow at tlm entrance to the 
source IMP in the event of imminent congstion at the 
destination. This usually requires that l separate 
proxfision be made in the algorithm to protect short 
interactive messages from experiencing unnecessarily 
high delays. 
Routing 
Network routing: strat,gies for distributect networks 
require routing de. cisons to Dr. made with only in- 
formation available to an I5II' and the IMP must 
------------------------------<page break>-----------------------------
Computer Communication Network Design 261 
execute those decisions to effect the routing) .' A 
simple (:xamp}e of such a strategy is to have each IMP 
handling a packet indcpcndcntly route it along its 
current, estimatc of the shortest path to the destination. 
I,'or many applications, it suffices to deal with an 
idealized routing strategy which may not simulate the 
IMI' routing functions in detail or which uses informa- 
tion not available to the IMP. The gcneral propcrties 
of both strategies are usually similar, differing mainly 
in certain implementation details such as the avail- 
ability of buffers or the constraint of counters and the 
need for the routing to quickly adapt to changes in 
IMP and circuit status. 
The IMPs perform the routing computations using 
information received from other IMPs and local 
information such as the alive/dead state of its circuits. 
In the normal case of time varying loads, local informa- 
tion alone, such as the length of internal queues, is 
insufficient to providc an efficient routing strategy 
wittrout assistance from the neighboring IMPs. It is 
possible to obtain sufficient information from the 
:.:i.qh'.:;'a to provide efficient routing, with a small 
amount of computation needed per IMP and without 
each IMP requiring a topological map of the network. 
In certain applications where traffic patterns exhibit 
regularity, the use of a central controller might be 
preferable. However, for most applications which 
involve dynamically varying traffic flow, it appears 
that a central controller cannot be used more effectively 
than the IMPs to update routing tables if such a 
controller is constrained to derive its information via 
the net. It is also a less reliable approach to routing 
than to distribute the routing decisions among the 
15{ Ps. 
The routing information cannot be propagated about 
the net in sufficient time to accurately characterize the 
instantaneous traffic flow. An efficient algorithm, there- 
fore, should not focus on the movcme. nt of individual 
packets, but rather use topological or statistical in- 
formation in the selection of routes. For example, by 
using an averaging procedure, the flow of tmfflc can be 
made to build up smoothly. This allows the routing 
algorithm ample time to adjust its tables in each IMP 
in advancc of the build-up of traffic. 
The scheme originally used in the ARPA network 
bd each IMP select one output line per destination 
onto which to route packets. The line was chosen to be 
the one with minimum estimated time delay to tbc 
de. stinatiou. The sclectiot was updated every half 
seco,Ld using minimum time estimates from the neigh- 
boring IMPs and internal estimates of the delay to each 
of thc neighbors. Even though the routing algorithm 
only selects one line at a time per destination, two 
output lines will be used if a qucue of packets waiting 
transmission on one line builds up before the routing 
update occurs and another line is chosen. Modifications 
to the scheme which allow several lines per destination 
to be used in an update interval (during which the 
routing is not changed) are possible using two or more 
time delay estimates to select thpath . 
In practice, this approach has'{i'6rked quite effectively 
with the moderate levels of traffic experienced in the 
net. For heavy traffic flow, this strategy may be 
inefficient, since the routing information is bmsed on 
the length of queues, which we have seen can change 
much faster than the information about the clmngc 
be distributed. Fortunately, this information is still 
usable, although it can be substantially out of date and 
will not, in general, be helpful in making efficient 
routing decisions in the heavy traffic case. 
A more intricate scheme, recently developed by 
BBN, allows multiple paths to be efficiently used even 
during heavy traffic. s Preliminary simulation studies 
indicate that it can be tailored to provide efficient 
routing in a network with a variety of heavy traffic 
conditions. This method separates the problem of 
defining routes onto which packets may bc routed from 
the problem of selecting a route when a particular 
packet must bc routed. By this technique, it is possible 
to send packets down a path with the fewest IMPs and 
excess capacity, or when that path is filled, the one with 
the next fewest IMPs and excess capacity, etc. 
A similar approach to routing was independently 
derived by NAC using an idealized method that did not 
require the IMPs to participate in the routing decisions. 
Another approach using a flow deviation technique has 
recently been under study at UCLA.  The intricacies of 
the exact approach lead to a mctcring procedure that 
allows the overall network flow to bc changed slowly for 
stability and to perturb existing flow patterns to obtain 
an increased flow. These pprochcs all possess, in 
common, essential ingredients of a desirable routig 
strategy. 
Topological consideratiozs 
An efficient topological design provides a high 
throughput for a given cost. Alth6ugh many measures 
of throughput are possible, a convcnic. nt one is the 
average amount of traffic t. hata single IMP can send 
into the network when all othcr IMPs arc transmitting 
according to a specified traffic pattern. Often, it is 
assumed that all other IMPs are behaving identically 
and each IMP is sending equa! arnourns of traffic to 
each othc. r IMP. Tile comtraints on the topological 
design arc the available common carrier circuits, tbc 
target cost or throughput, the desired reliability, and 
------------------------------<page break>-----------------------------
262 Spring Joint Computer Conference, 1972 
TABLE 1--23 Node 28 Link ARPA 
Nnmbcr of Number of 
Circuit Combination8 
Failed to be Examined 
Number of 
Cuct 
28 1 
27 28 
26 378 
25 3276 
24 20475 
23 98280 
22 376740 
21 1184040 
20 3108105 
19 6906900 
18 13123110 
17 21474180 
16 30421755 
15 37442160 
14 40116600 
13 37442160 
2 30421755 
II 21474180 
10 13123110 
9 5906900 
8 3108108 
7 1184040 
1 
28 
378 
3276 
20475 
98280 
376740 
1184040 
3108105 
6906900 
13123110 
21474180 
30421755 
37442160 
40116600 
37442160 
30421755 
21474180 
13123110 
6906900 
3108108 
1184040 
6 376740 349618 
5 98280 70547 
4 20475 9852 
3 3276 827 
2 378 30 
1 28 0 
the cost of computation required to perform the 
topological design. 
Since, there was no el('.r specification of the. amount 
of traffic that the network would ]lave to accommodate 
initially, it was first constructed with enough excess 
capacity to accommodate any reasonable traffc require- 
merits. Then as ncw IMPs were added to the system, 
the capacity was and is still being systematically 
reduced until the traffic level occupies a substantial 
fraction of the nctwork's total capacity. At this point, 
the net's capacity x4ll bc increased to maintain the 
desired percentage of loading. At the initial stages of 
network design, the "two-connected" reliability con- 
straint essentially determined a minimum value of 
maximum throughput. This constraint forces tile 
average throughput to be in the range 10-15 kilobits per 
second Rcr IMP, when 50 kilobit/svc circuils are used 
throughout the network, since two commuaication 
paths between every pair of IMPs are needed. Alterac- 
tively, if this love,1 of throughput is rvquircd, then the 
reliability specification of "two-co]mectiviu'" can bc 
obtained without additiouM cost. 
Reliability computations 
A simple and natural characterization of network 
reliability is the ability of the ne. twork to sustain 
communication between all operable pairs of IMPs. For 
design purposes, the requirement :oJ..twct independent 
paths between nodes insures that at least two IMPs 
and/or circuits must fail before any pair of operable 
IMPs cannot communicate. This criterion is independent 
of the properties of the IMPs and circuits, does not take 
into account the "degree" of disruption that may occur 
and hence, does not reflect the actual availability of 
resources in the network. A more meaningful measure 
is the average fraction of IMP pairs that cannct com- 
municate because of IMP and circuit failures. This 
calculation requires knowledge of the IMP and circuit 
failure rates, and could not be performed until enough 
operating data was gathered to make valid predictiota. 
To calculate network reliability, wc must consider 
elementary network structures known as cutsets. A 
.34 
.3z C 
IMPS AND 
CIRCUITS FALLING 
.26 
.1 2 IMP FAILURES 
CIRCUIT FAI RES 
.06 ONLY  
.04 
,O2 
O 
O 
.02 .O5 .O4 ,05 ,O6 ,07 .O8 .09 
PROBABILITY OF ELEMENT FALLING 
Fignre 2--Network availabiliLy rs. IMP and circuit re iability 
------------------------------<page break>-----------------------------
Computer Communication Network Design 263 
cutset is a set of circuits and/or IMPs whose removal 
from the network breaks all communication paths 
between at least two operable IMPs. To calculate 
reliability, it is often the ctme that all cutsets must be 
either enumerated or estimated. As an example, in a 
23 IMP, 28 circuit ARPA Network design similar to 
the one shown in Figure led), there are over twenty 
million ways of deleting only circuits so that the 
remaining network has at least one operable pair of 
IMPs Mth no intact communication paths. Table 1 
indicates the numbers of cutsets in the 23 IMP network 
as a function of the number of circuits they contain. 
A combination of analysis and simulation can be 
used to compute the average fraction of non-com- 
municating I.MP pairs. Detailed descriptions of the 
analysis methods are given in Reference 44 while their 
application to the analysis of the ARPANET is dis- 
cussed in Reference 43. The results of an analysis of 
the 23 IMP version of the network are shown in Figure 
2. The curve marked A shows the results under the 
assumption that IMPs do not fail, while the curve 
marked B shows the case where circuits do not fail. 
The curve marked G assumes that both IMPs and 
circuits fail with equal probability. In actual operation, 
the average failure probability of both IMPs and 
circuits is about 0.02. For this value, it can be seen that 
the effect of circuit failures is far less significant than 
the effect of IMP failures. If an IMP fails in a net:ork 
Mth n IMPs, at least n-I other IMPs cannot com- 
municate with it. Thus, good network design carmot 
improve upon the effect directly due to IMP failures, 
which in the ARPANET is the major factor affecting 
the reliability of the communications. Further, more 
intricate reliability analyses which consider the loss of 
throughput capacity because of circuit failures have 
also been performed and these losses have been shown 
to be negligible. ts Finally, unequal failure rates due to 
differences in line lengths have been shown to have 
only minor effects on the analysis and can usually be 
neglected? 
Topological optimization 
During the computer optimization process, the 
reliability of the topology is assumed to be acceptable if 
the network is at least two-connected. The object of 
the optimization is to decrease the ratio of cost to 
throughput subject to an overall cost limitation. This 
technique employs a sophisticated network optimization 
program that utilizes circuit exchange heuristics, 
routing and flow analysis algorithms, to generate low 
cost designs. In addition, two time delay models were 
initially used to (1) calculate the throughput torre- 
sponding to an average,. time delay of 0.2 seconds, 
(2) estimate the packet rejection rate due to all buffers 
filling at an IMP. As experience with these models 
grew, the packet rejection rate was found to be negligible 
and the computation discontinued. The delay computa- 
tion (Equation (7) in a later section) was subsequently 
first replaced by a heuristie:-.ealculation to speed the 
computation and later eliminated after it was found 
that time delays could be guaranteed to be acceptably 
low by preventing cutsets from being saturated. This 
"threshold" behavior is discussed further in the next 
section. 
The basic method of optimization was described in 
Reference 12 while extensions to the design of large 
networks are discussed in Reference 9. The method 
operates by initially generating, either manually or by 
computer, a "starting network" that satisfies the overall 
network constraints but is not, in general, a low cost 
network. The computer then itertively modifies the 
starting network in simple steps until a lower cost 
network is found that satisfies the constraints or the 
process is terminated. The process is repeated until no 
further improvements can be found. Using a different 
starting network can result in a different solution. 
However, by incorporating sensible heuristics and by 
using a variety of carefully chosen starting networks and 
some degree of man-machine interaction, "excellent" 
final networks usually result. Experience has shown 
that there arc a wide variety of such networks Mth 
different topological structures but similar cost and 
performance. 
The key to this design effort is the heuristic procedure 
by which the iterative network modifications are made. 
The method used in the ARPANET design involves the 
removal and addition of one or two circuits at a time. 
Many methods have been employed, at various times, 
to identify the appropriate circuits for potential addi- 
tion or deletion. For example, to delete uneconomical 
circuits a straightforward procedure simply deletes 
single circuits in numerical order, reroutes traffic and 
reevaluates cost until a decrease in cost per megabit is 
found. At this point, the deletion is made permanent 
and the process begins again. A somewhat more 
sopkisticated procedure deletes circuits in order of 
increasing utilization, while a more complex method 
attempts to evaluate the effect of the removal of any 
circuit before any deletion is attempted. The circuit 
with the greatest likelihood of an improvement is then 
considered for removal and so on. 
There are a huge number of reasonable heuristics for 
circuit exchanges. After a area! deal of experimentation 
5th many of these, it appears that the choice of a 
particular heuristic is not critical. Instead, the speed 
and efi%iency Sth which potential exchanges can be 
------------------------------<page break>-----------------------------
204 Spring 3oint Computer Conference, 1.072 
investigated appears to t,. !he limiting factor affccl 
the qualily f the final design. I"mally, ts the size 
the nrqwork increases, the eatr'r the cost becomes 
perform any circuit exchange optimizalion. Decem- 
position of the network design inlo regions becomes 
necessary and additional heuristics are m'eded to 
determine eectivc dccomposit ioas. I t presently appears 
that these methods can be used to design relatively 
ccicnt nctworks with a few hundred IMPs while 
substantially ne.w procedures will be necessary for 
networks of eatcr size. 
The topolocal design requires t routing algorithm 
to evalusts the throughput capability o any given 
network. Its properties must reflect those o[ an 
plementable routing algorithm, for example, within 
the ARPANET. Although the routing problem can be 
formulated as a "multicommodity flow problem '" and 
solved by linear pro,staining for networks with 230 
IMPs/fstcr techniques are ncedcd when the routing 
,El --i,hm is incorporated in a design procedure. Tho 
dign procedure for the ARPA Network topology 
itert;-cb, analyzes thousands of networks. To satisfy 
he requirements for speed, an algorithm which 
selects the leasL uLilized path qth the minimum number 
of IMPs was initially used? This algorithm was lator 
replaced by one which sends as much franc as possible 
along such paths until one or more circuits apprsach a 
few percent of full uLilization? These highly utilized 
circuits are then no longer allowed to carry additional 
flow. Iraread, new parks with excess capacity and 
possibly more intermediate nodes arc found. The 
procedurc continues until some cutset centaim only 
nearly fully utilized circuits. At this point no additional 
flow can bc sent. For design purposes, this Mgorithm 
a highly satisfactory replacement for the more com- 
plicaLed multi-commodity approach. Using Lhe 
gertthru, i h been shown that the throughput capa- 
bilities of hc ARPA Network arc substantially 
imexsitivc to the distribution of ra$c and depend 
mainly only on the Lotat trac flow within ;he ncm'ork. s 
Aaytic models of xtwork pcrformacc 
The effort to determine analytic models of system 
performance has proceeded in two phases: (1) the pre- 
diction of averag(, time, delay encountered by a message 
as it passes through the network, and (2) the use of 
these qucueing models to calculate optimum channel 
capacity assignments for minimum possible delay. The, 
model used as a standard for the average message delay 
was first described in I-icfcrence 21 where i served o 
predict delays in stochastic communication networks. 
In I{eferencc 22, il was modifi'd 1, d'scrit,. the 5c- 
havinr of ARl'A-like computer m.lxxrks whih. 
Reference 23 il was refim'd further to apply directly 
the AIlPAN ET. 
The single server model 
Queueing theor3 a provides an effective set of ana- 
lytical tools for studying packtq &'lay. Much of this 
theory considers systems in which messages place 
demands for transmission (service) upon a single 
communication ehannc! (the single server). These 
systems are charaelcrizcd by A (r), the distribution of 
interarrival times between demands and B(I), lhe 
distribution of service times. When th, average demand 
for service Js less than the capacity of the channel, the 
system Js said to be stable. 
When A (r) is exponential (i.e., Potsson arrivals), 
and messages are traasmitted on a first-come first-served 
basis, the average time T in the stabh, system is 
r-- +[ (1) 
where X is the average arrival rate of messages, [ and  
are the first and second moments of B(I) rcspr'ctiw,ly, 
and p= hi< 1. If the service time is also exponential, 
T= (2) 
When A (r) and (t) arc arbitrary distribmios, the 
situation becomes comph,x and only weak results arc 
available. For example, no expression is available for T: 
however the foliowhig upper bound yields an excellent 
approximation  as 1: 
where a? and o;: arc the variance of the interarrival 
time and serv/ce time distribution& respectively. 
Networks of queues 
Multiple. channels in a network environment give 
rise to queueing problems that are far mort' difficult to 
solve than single server systems. l:or examph', the 
variability in the clioice of source and destination for a 
message is a network phenomenon which contributes to 
de. lay. A principal analytical difficulty resuP, s from the 
fact l}11).i flows throughout the nelwork are eorrehded. 
The basic approach to solving these stochastic network 
------------------------------<page break>-----------------------------
Computer Communication Network Design 265 
problems is to decompose them into nalyzable single- 
server problems which reflect thc original network 
structure and traffic flow. 
Early studies of qucucing networks indicated that 
such a decomposition ws poible; .a' however, those 
results do not carry over to message s5tchcd computer 
networks duc to the correlation of traffic flows. In 
Reference 21 it was shown for a wide variety of com- 
mumcation nets that this correlation could bc removed 
by considering the length of a given packet to bc an 
independent random variable as it presses from node to 
node. Although this "independence" assumption is not 
physically realistic, it results in a mathematically 
tractable model which does not sccm to affect the 
accuracy of the predicted time delays. As the size and 
connectivity of the network increases, the assumption 
becomes increasingly more realistic. With this assump- 
tion, a successful decomposition which permits a 
channel-by-channel analysis is possible, as follows. 
The packet delay is defined s the time which a 
pacnct spends in the network from its entry until it 
reaches its destination. The average packet delay is 
;:n>ted as T. Let Zi} be the average delay for those 
packets whose origin is IMP j and whose destination is 
IMP k. Wc assume a Poisson arrival process for such 
packets with an average of %.} packets per second and 
an exponential distribution of packet lengths with an 
average of 1/ bits per packet. With these definitions, 
if , is the sum of the quantities ,}, then : 
Let us now reformulate Equation (4) in terms of 
single channel delays. Wc first define the following 
quantities for the ith channel: C as its capacity 
(bits/second); X as the average packet traffic it carries 
(packets/second); and T,. as the average time a packet 
spends waiting for and using the ith channel. By 
relating the {X} to the {'i}] via the paths selected by 
the routing algorithm, it is csy to scc that : 
T=  X_, T, (S) 
With the assumption of Poisson traffic and exponential 
service times, the quantities T are given by Equation 
(2). For an average packet length of l/ bits, = 1/iC 
seconds and thus 
1 
T= ,C,.- X; (6) 
Thus we have successfully decomposed the analysis 
problem into a set of simple single-channel problems, 
A refinement of the decomposition permits a non- 
exponential packet length distribution and uses Equa- 
tion (1) rather than Equation (2) to calculate T; 
as an approximation, the Markovian character of the 
traffic is sumed to be preserved. Furthermore, for 
computer networks we include the effect of propagation 
time and overhead traffic to obtain the folloMng 
equation for average packet lay 
X,[,1 X,/C, ] 
T=X+ ( +C,_x+P,+K (7) 
Here, 1/' represents the average lenh of a Host 
packct, and 1/ represents the average lenh of all 
packets (including acknowledgmcnts, headcrs, requests 
for next messages, parity cheeks, etc.) within the net- 
work. The expreion 1/'C+ E(X/C)/(C- X) 
represents the average packet delay on the ith channel.' 
The term (X/C)/(C-X) is the average time a 
packet spends waiting at the IMP for the ith channel to 
become available. Since the packe must compete 5th 
acknowledgments and other overhead raffic, the 
overall average packet lenh 1/ appears in the 
expression. The term 1/'C is the time required to 
trammit a packet of average lenh '. Finally: K is 
the nodal processing time, sumed corotant, and for 
the ARPA IMP approximately equal to 0.35 ms; 
P is the propagation time on the ith channel (about 
20 ms for a 3 le channel). 
Assuming a relatively homogeneous set of C and 
P, no indihdual erm in the exprcssion for delay 
dominate he summation until he flow X/ in onc 
channel (say channel i,) approaches the capacity C.. 
At that point, the term T., and hence T will ow 
rapidly. The expression for delay is then dominated by 
one (or more) terms and exhibits a threshold behaor. 
Prior to this threshold, T reinaim relatively corotant. 
Thc accuracy of the timc delay model, as wclt as this 
threshold phenomenon was dcmotrated on a 19 node 
network  and on the ten node ARPA net derived from 
Fibre l(c) by deleting the rightmost five IMPs. 
Using the routing procedure described in the last 
section TM and equal traffic bctween all node pairs, the 
channel flows X,. wcre found for the cn node net and 
the delay curves shown in Fibre 3 were obtained. 
Curve A was obtained with fixed 10 bit packets,* 
while curve B was generated for exponentially dis- 
t. ributed variable lenh packets with average size of 
5 bits. In both cases A and B, all overhead factors 
were ignored. Note that the delay reinaim small until a 
 In ee A, the application of Equation (1) allows for constant. 
packet lengfim (i.e., zero variance). 
------------------------------<page break>-----------------------------
266 Spring Joint Computer. Conference, 1972 
DELAY (SEC) 
r" BIT PACKETS PLUS OVERHEAD 
 I {I \ : 1000BIT PACKETS PLUS OVERHEAD 
/--1OOO BIT PACKETS WITHOUT OVERHEAD 
--50O BIT PACKETS WITHOUT OVERHEAD 
Figure 3--Detay vs. throughput 
total throughput slightly greater than 400 kilobits/ 
second is reached. The delay then increases rapidly. 
Curves C and D respectively represent the same 
situations when the overhead of 136 bits per packet and 
per RFNM and 152 bits per acknowledgnent are 
included. Notice that the total throughput per IMP 
is reduced to 250 kilobits/second in case C and to 
approximately 200 kilobits/se. cond in case D. 
In the same figure, we have illustrated with z's the 
results of a simulation performed with a realistic 
routing and metering strategy. The simulation omitted 
all network overhead and assumed fixed lengths of 
1000 bits for all packets. 
It is difficult to develop  practical routing and flow 
control procedure that will allow each IMP to input 
identical amounts of traffic. To complete the d('lay 
curve A Mth the points obtained by simulation, 'the 
curve should .actually be recomputed for the slightly 
skewed distribution that resulted. It is notable that the 
delay estimates from the simulation (which used a 
dynamic routing strategy) and the computation (which 
used a static routing strategy and the time delay for- 
mula) are in close agreement. I n particular , the5, both 
accurately determined the vert{:l rise of the delay 
curve in the range just above 400 kilobits/second, the 
formula by predicting infinite delay and the simulation 
by rejecting the further input of traffic. 
In practice and from thc analytic and simulation 
studies of the ARPANET, the average qucueing delay 
is observed to remain small (almost that of an unloaded 
net) and well within the design constraint of 0.2 seconds 
until the traffic within the network approaches the 
capacity of a cutset. The delay then increases npidly. 
Thus, as long as trafc is low enough and the rou.ti?g 
adaptive enough to avoid the premature saturation of 
cutsets by guiding trac along paths with excess capacity, 
queueing delays are not significant. 
Channel capacity optimization 
One of the most difficult design problems is the 
optimal selection of capacities from a finite set of 
options. Although there are many heuristic approaches 
to this problem, analytic results are reladw,ly scarce. 
(For the specialized case of centralized networks, an 
algorithm yielding optimal results is available) ) While 
it is possible to find an economical assignment of 
discrete capacities for, say, a 200 IMP network, very 
little is known about the relation between such capacity 
ignments, message delay, and cost. 
To obtain theoretical properties of optimal capacity 
assignments, one may ignore the corottaint that 
capacities are obtainable only in discrete sizes. 
Reference 21 such a problem was posed where the 
network topology and average traffic flow were assumed 
to be known and fixed and an optimal match of capaci- 
ties to traffic flow was found. Also, the trac was 
assumed to be Markevian (Polsson arriwds and 
exponential packet h,ngths) and the indvprndence 
assumption and decomposition method wen' applied. 
For each clmmwl, the capacity C was found which 
minimized the average message delay T, at a fix<,(l 
total system cost D. Since Xdu is the aw,rage bit raw 
the. ith channel, thv solution to a!/optimal assignment 
problem must provide more than this minimal capacity 
to each channel. This is ch,ar sine(, both Equations 
and (7) indicale that T will become arbitrarily large 
with less tan (or equal to) this amount of ca)mcily. 
It is not critical exacfiy how the czccss capacity 
------------------------------<page break>-----------------------------
Computer Communication Network Design 267 
ssigned, a.q long ms C,>X,I. Other important param- 
s!tess and insights have been identified'in studying the 
continuous capacity optimization problem. For ex- 
ample, the number of excess dollars, D,, remaining 
after the minimum capacity X,/ is ressigned to each 
channel is of gret importance. As D,--,0, the average 
delay must grow arbitrarily large. In this range, the 
critical parameters become p and fi where p=-/uC is 
the ralio of the rate -/ at which bits enter the network 
to the rate C at which the net can handle bits and 
fi = X/% where X = X is the total rate at which packets 
flow Mthin the net. The quantity  represents a dimen- 
sionless form of network "lead" whereas fi is esily 
shown to represent the average path length for a 
packet. 
As the lead p approaches lift, the delay T grows very 
quick}y, and this point = I/fi represents the maximum 
lead which the network can support. If capacities are 
assigned optimally, all charmels saturate simultaneously 
at this point. In this formulation fi is a design parameter 
which depends upon the topology and the routing 
proce'h:re, while  is a parameter which depends upon 
the ,,put rate and the total capacity of the network. 
In studying the ARPANET  a closer representation 
of the actual tariffs for high speed telephone data 
channels used in that network was provided by setting 
D= dC where 0<a<l.* This approach requires 
the solution of a non-linear equation by numerical 
techniques. On solving the equation, it can be shown 
that the packet delay T varies insignificantly with a 
for .3_<a_<l. This indicates that the closed form 
solution discussed earlier with a= 1 is a reasonable 
approximation to the more difficult non-linear problem. 
These continuous capacity studies have application to 
general network studies (e.g., sateIll te communications) = 
and are under continued investigation. ." 
In practice, the selection of channel capacities must 
be made from a small finite set. Although some theo- 
retical work hs been done in this cse by approxi- 
mating the discrete cost-capacity functions by 
continuous ones, much remains to be done. a. Because 
of the discrete capacities and the time varying nature 
of network traffic, it is not generally possible to match 
channel capacities to the anticipated flows within the 
channels. If this were possible, all channels would 
saturate at the same externally applied lead. In.stead, 
capacities are assigned on the basis of reasonable 
estimates of average or peak traffic flows. It is the 
respomibitity of the routing procedure to permit the 
traffic to adapt to the available capacity? Often two 
 Oi course the tariffs reflect the discrete nature of available 
channel*. The use of the exponent  provid a continuou fit 
to the discrete cost function. For the AP. PANET, a_.8. 
IMP sites MII engage in heavy. communication and 
thus saturate one or mort, critical network cutsets. In 
such eases, the routing MII not be able to send addi- 
tional flow across these cuts. The network will therefore 
experience "premature" saturation in one or a small set 
of channels leading to the threshold behavior described 
earlier.  :. - 
DISCUSSION 
A major conclusion from our experience in network 
design is that message sftched networks of the ARPA 
type are no longer difficult to specify. They may be 
implemented straightforwardly from the specifications; 
they can be less expensive than other currently available 
technical approaches; they perform remarkably well as 
a communication system for interconnecting time- 
sharing and batch processing computers and can be 
adapted to directly handle teletypes, displays and many 
other 'kinds of terminal devices and data processing 
equipment? . 
The principal tools available for the design of net- 
works are analysis, simulation, heuristic procedures, 
and experimentation. Armtysis, simulation and heuristics 
have been the mainstays of the work on modeling and 
topological optimization while simulation, heuristic 
procedures and experimental techrdques have been the 
major tools for the actual network implementation. 
Experience has shown that all of these methods are 
useful wkile none are all powerful. The most valuable 
approach has been the simultaneous use of several of 
these tools. 
Each approach has room for considerable improve- 
ment. The analysis efforts have not yet yielded results 
in many important areas such as routing. However, for 
prediction of delay, tkis approach leads to a simple 
threshold model which is both accurate and under- 
standable. Heuristic procedures all suffer from the 
problem that it is presently unclear how to select 
appropriate heuristics. It has been the innovative use 
of computers and amfiysis that has made the approach 
work well. For designing networks with no more than a 
few hundred IMPs, present heuristics appear adequate 
but a good deal of additional work is required for net- 
works of greater size. Simulation is a well developed tool 
that is both expensive to apply and limited in the overall 
understanding that it. yields. For these re.sons, simula- 
tion appears to be most useful only in validating models, 
and in asisting in dettdled design decisions sueIt as the 
number of buffers that an IMP should contain. As the 
size of networks continues to grow, it appears that 
simulation will become virtuMly useless as a total desil: 
tool. The ultimat.c standard by wlxich all models and 
------------------------------<page break>-----------------------------
258 Spring .Ioint Computer Conference, 1972 
cemclusions can be l'sted is 'Xl)erimv,tatiem. Experi- 
ment.arian with the aetua} network is conceptually 
relatively straightforward and w'ry useful. Although, 
experiments are often 1ogisticMly difficult t.o perform, 
they can proide an (.sy means f,r testing 
}wuristics md design parameters. 
The outstanding design pmbiems currently facing 
the network designer are to sl)ecify and determine the 
properties of the routing, flow control and topological 
structure for htrge. networks. This specification must 
m: ke full use of a wide variety of circuit options. 
Preliminary studies indicate that initially, the most 
fruitful approaches wil} bc based on the partitioning 
th(, network into regioxs, or equivalently, coxstructing 
a large network by connecting l[ number of regionM 
networks. To send a roessag(', a I-test woukl specify 
both the destition rcon and the destination IMP 
in that re,on. No detailed implementation el a large 
network h yet been specified but carly .studies of their 
properties indicate that facto such as cost, throughput, 
delay and reliability are similar to those of thc present 
ARPANET, if the ARPA technology is used? 
''cc;, quc; applicable to the design of large networks 
are presently under intexsire study. These techniques 
appear to split into the same four categories  sinai} 
network design but approaches may differ significantly. 
For example, large nets are likely to demand the pkmc- 
ment of high bandwidth circuits at certain key iaeatiara 
in the topology to concentrate flow. These circuits will 
require the development of a high speed IMP to connect 
them into the net. It is likely that. this high speed IMP 
xdll have the structure of a high speed multiplexer, and 
may rcquirc several cooperaling processors to obtain 
the needed computer power for the job. Flow control 
stratees for large networks seem to extrapolate nicely 
from small network strategies if each region in the large 
network is dewed as a node in a smaller network. 
However, this area will require additional study as 
the problem of specifying effective adaptive routing 
mechanisms. Recent efforts indicate that, efficient 
practical so}wines for sm:d] networks will soon 
available. These schemes seem to be applicable for 
adaptive routing and flow control in networks con- 
strutted from regional subnetworks. The development 
of practical algorithms 1o handle routMg and flow 
control is still an art rather than a science. Simulation is 
useful for studying the properties of a given heuristic, 
but intuition still plays a dominant role in the system 
design. 
S,vcral open questions in network design presently 
are: (I) what slructurv should a high bandwidlh 
bandwidth circuits: lB) how s}lou]d large ,vlworks 
partitioned for both vffectivv design and operation; 
lind (4) what operational procvdur.s shemid large 
networks follow? Much work has :dready been done in 
these areas but much mary remains to by d,ne. We 
expect subst.'mtial progress to by achi'ved in the next 
few years, and ltccordingly, the increased underst:mding 
of tM. properties of mvss,'tgc switched networks of 
all sizes. 
ACKNOWLEDGMENT 
Th, ARPA Network is in large' parl lhe conception of 
Dr. L. G. Roberts of the' Advanced Resparch Projects 
Agency to whom wv owe a debt of atitude for his 
support and ,ncouragemenl. We also acknowledge 
helpful contributi(ms of S. Crock,r and B. Dolan of 
ARPA. At BBN, NAC, and UCLA many individuals, 
too numerous to lisl, participated in the network effort. 
and we atefully acknowledge their contributions. 
REFERENCES 
1 P BARAN S BOEItM P SMITIt 
On distributed communication* 
Series of 11 reports by Rand Corporation Santa Monica 
California 1964 
"Spccification. for thc intcrcanncctfon of a Host and 
an IMP 
BBN lieport No 1822 1971 revision 
S CARl{ S CROCKEl{ V CERF 
Host-Host communication protocol in the ARPA network 
SJCC 1970 pp 589-597 
S CROCKEl{ et a] 
Function oriented protocols for the ARPA network 
SJCC 1972 in this issue 
D W DAVIES 
The canteel of cangcslion m pca:ket swiLching networks 
Proc of the Second ACM IEEE Symposi:,m on problems 
in the Optimization of Data Communications Systems 
Pale Alto California Oct 1971 pp 4649 
D FAI'.BER K LARSON 
The archftccturc of a distributcd computer systcm--An 
informal description 
U,fivcrsity of California Irvine Information and 
COmlm(Cr Science Tech.ical lieport 'I 1 1970 
W D FAIIMER E E NEWIIALL 
A n czpcrimcnta! d[st'ibution u, itchmg ytcm to handle 
bursly compulcr lrsjc 
Proc of the ACM Syml)osium on Problems in the 
Opt:nuzatm. o. r i)atl[ CtmmmuicaLio,, Systems 1969 
lip 1-34 
11 FRANK W CItOU 
Routing in eo?npller nctwors 
Networks John Wilcy 1971 Yol I N. 2 pp 99-1!2 
It FI[ANK W CIIOU 
Cos! and throlghp.t in compulcr-commlmicallon lclworks 
To npper in the lnfot,,vh 11eport tm the State of the 
Art of Computer Netw{rks 1972 
II I"liANI( I T I"IllSC]I 
ConmzunicaDo transmission and trasportatWl nclworks 
Addhon Wley t972 
------------------------------<page break>-----------------------------
Function-oriented protocols for the ARPA Computer Network 
by STEPHEN D. CROCKER 
Advanced Research Project A ency 
Arlington, Virginia 
and 
JONATHAN B. POSTEL 
University of California 
Los Angeles, Californit 
JOHN F. HEAFNER 
The RAND Corporation 
Santa Mon ca, California 
ROBERT M. METCALFE 
Massachusetts Irutitute of Technology 
Cambhdgc, Maachusett 
INTRODUCTION 
Much has been said about the mechanics of the ARPA 
Compuler Network (ARPANET) and especially about 
the organization of its communications subnet. .:,..a 
Until recently the main effort has gone into the imple- 
mentation of an ARPANET user-level communications 
interface. Operating just above the communications 
subnet in ARPANET HOST Computers, this ARPA- 
NET interface is intended to serve as a foundation for 
the organization of function-oriented communica- 
tions. ',? See Figures t and 2 for our view of a computer 
system and the scheme for user-level process-to-process 
communications. It is now appropriate to review the 
development of protocols which have been constructed 
to promote particular substantive uses of the 
ARPANET, namely function-oriented protocols. 
We should begin this brief examination by stating 
what we mean by the word "protocol" and how proto- 
cols fit in the plan for useful work on the ARPANET. 
When we have two processes facing each other across 
some communication !ink, the protocol is the set of 
their agreements on the format and relative timing of 
messages to be exchanged. When we speak of a proto- 
col, there is usually an important goal to be fulfilled. 
Although any set of agreements between cooperating 
(i.e., communicating) processes is a protocol, the proto- 
cols of interest are those which arc constructed for 
general application by a large population of processes 
in solving a large class of problems. 
In the understanding and generation of protocols 
there are two kinds of distinctions made. Protocols in 
the ARPANET are layered and we speak of high or 
low level protocols. High level protocols are tho.se most 
closely matched to functions and low level protocols 
deal with communications mechanics. The lowest level 
software protocols in the ARPANET involve reliable 
message exchange- between ARPANET Interface 
Message Processors (IMPs). TM A high level protocol is 
one with primitives closely related to a substantive use. 
At the lowest levels the contents of messages are un- 
specified. At higher levels, more and more is stated 
about the meaning of message contents and timing. The 
layers of protocol are shown in Figure 3. 
A second way of structuring sets of protocols and 
their design is bound up in the word factoring. At any 
level of protocol are sets of format and timing rules 
sociated with particular groupings of agreements. In 
the IMPs we find certain protocols pertaining to error 
handling, while others to flow control, and still others 
to message routing. At the ARPANET's user-level 
communications interface there are, among others, 
separable protocols associated with 
neetions and logical data blocking. These potocols do 
not nest, but join as modules at the same level. 
Before moving on to consider the higher ]cvel func- 
tion-oriented protocols, let us first make a few state- 
ments about underlying protocols. There are three 
lower level software protocols which nest in support of 
the user-le,el communications interface for the ARPA- 
NET. The lowest of these is the IMP-IMP protocol 
which provides for reliable communication among 
IMPs. This protocol handles transmission-error detec- 
tion and correction, flow control to avoid message 
congestion, and routing. At the next higher level is the 
IMP-HOST protocol which provides for the passage 
of messages between HOSTs and IMPs in such a way 
a to create virtual communication paths between 
HOSTs. With IMP-HOST protocol, a HOST ha 
operating rules which permit it to send messages to 
specified HOSTs on the ARPANET and to be informed 
of the dispensation of those mcages. In particular, the 
IMP-HOST protocol comstrairm HOSTs in their trans- 
nkssons so that they can make good use of available 
271 
------------------------------<page break>-----------------------------
272 Spring Joint Computer Conferencc,.1972 
!!i{ii!?i!!il ..... i!i!!i!!) ":'::iii!i{i?i{!!!i:. Centre 1 
::::::::::::::::$::)F::::::::: Process :ii:!:!i!:! Process 
============================== .::':::::':::: :::::::::::::::::::::: P r o g ram 
' Terminal Control >:':/ File System 
Te rmi ns 1 
Terminal 
Operating 
System 
Boundary 
Figure 1--Our view of a computer system 
communications capacity without denying such avail- 
ability to other HOSTs. 
The HOST-HOST protocol, final]y, is the set of 
rules whereby HOSTs construct and maintain com- 
munication between processes (user jobs) running on 
remote computers. One process requiring communica- 
tions with another on some remote computer system 
makes requests on its local supervisor to act on its 
behalf in establishing and maintaining those communi- 
catlens under HOST-HOST protocol. 
In constructing these low levels of protocol it was the 
intention to provide user processes with a general set 
of useful comanunication primitives to isolate them 
from many of the details of operating systems and 
communications. At this user-level interface function- 
oriented protocols join a. an open-ended collection of 
modules to make use of ARPANET capabilities. 
The communications environment facing the de- 
signers of function-oriented protocols in the ARPANET 
is essentially that of a system of one-way byte-oriented 
connections. Technically speaking, a "connection" is a 
pair: a "send socket" at one end and a "receive socket" 
at the other. Primitives provided at the user-level 
interface include: 
1. Initiate connection (local socket,, foreign socket), 
2. Wait for connection (local socket), 
3. Send, Receive (local socket, data), 
4. Close (local socket), 
5. Send interrupt signal (local socket). 
Processes in this virtual process network can ereate 
connections and transmit bytes. Connections are sub- 
jeer to HOST-HOST flow control and the vagaries of 
timing in a widely distributed computing environment, 
but care ha been taken to give us(,,r processvs control 
over their communications so as to, make .rul! use of 
network parallelism and redundancy. The kind of 
agreements which must be made in the creation of 
------------------------------<page break>-----------------------------
Function-Oriented Protocols for ARPA Computer Network 273 
Use r '::i':':" '"... .'. . . , .' .:... :. '..:ii(!ii':::'--. . :.". '.......:.':[:::}:i:!! C on t r o 1 I 
Process :i:.:.i::!::::J:i!![!::?:ii::ii!li:.:.::!!i!iiiil - 
:?:i ::! togram P 
M '  C on t r o l .:i:!:!:!i:::i:ii:i: _ :::::::::::::::::::::: 
p ' .!"'"":---..?i?::iiiii:ii Pocess 
r r o g r ......... .,., ::::::::::::::::::::::::::::::::::::::::::::::::::::::::: 
Figure 2--Two communicating procees 
function-oriented protocols relate to rules for estab- 
lishing connections, to the timing rules which govern 
transmission sequences, and to the content of the byte- 
streams themselves. 
USE OF REMOTE INTERACTIVE SYSTEMS 
The.application which currently dominates ARPA- 
NET activity is the remote use of interactive _systems. 
A Telecommunications Network (TELNET) protocol 
is followed by processes cooperating to support this 
application.  A user at a terminal, connected to his 
local HOST, controls a process in a remote HOST as if 
he were a local user of the remote HOST. ttis local 
HOST copies characters between his terminal and 
TELNET connections over the ARPANET. We refer 
to the HOST where the user sits as the us/rig HOST, 
and to the remote HOST as the serving HOST. See 
Figure 4. 
At the using HOST, the user must be able to per- 
form the following functions through his TELNET 
user process ("user-TELNET"): 
1. Initiate a pair of connections to a serving HOST, 
2. Send characters to the serving HOST, 
3. Receive characters from the serving HOST, 
4. Send a HOST-HOST interrupt signal, 
5. Terminate connections. 
The user-TELNET needs to be able to distinguish be- 
tween (1) commands to be acted on locally and (2) 
input intended for the serving HOST. An escape char- 
acter is reserved to mark local commands. Conventions 
for the ARPANET Terminal IMP (TIP) user- 
TELNET are typical? 
In most using HOSTs, the above functions are pro- 
vided by a user-TELNET which is a user-level program. 
A minimal user-TELNET need only implement the 
above functions, but several additional support rune- 
------------------------------<page break>-----------------------------